[LeetCode] 994. Rotting Oranges(Kotlin)

[LeetCode] 994. Rotting Oranges(Kotlin)

• https://leetcode.com/problems/rotting-oranges/

풀이

• BFS

import java.util.Deque
import kotlin.math.*

class Solution {
    private var gridR = -1
    private var gridC = -1

    private val dirI = listOf(0,0,1,-1)
    private val dirJ = listOf(1,-1,0,0)

    private fun isInRange(i:Int, j:Int):Boolean{
        if((i < 0)||(gridR <= i)) return false
        if((j < 0)||(gridC <= j)) return false
        return true
    }

    fun orangesRotting(grid: Array<IntArray>): Int {
        val myGrid: List<MutableList<Int>> = grid.map{arr -> arr.toMutableList()}
        gridR = myGrid.size
        gridC = myGrid[0].size
        
        var rotTime = 0
        // queue of rotting oranges
        // <coordinate of orange in grid, time orange started to rot>
        var q = ArrayDeque<Pair<Pair<Int, Int>, Int>>()
        myGrid.forEachIndexed{i, row ->
            row.forEachIndexed{j, orange ->
                if(orange == 2) q.addLast(Pair(Pair(i, j), 0))
            }
        }
       
        val visited = List<MutableList<Int>>(10){MutableList<Int>(10){0}}

        // rot oranges adjacent to rotten oranges in q
        while(!q.isEmpty()){
            val curOrange: Pair<Int, Int> = q.first().first
            val i = curOrange.first
            val j = curOrange.second
            val curTime = q.first().second
            q.removeFirst()

            if(visited[i][j] == 1) continue

            rotTime = max(rotTime, curTime)
            myGrid[i][j] = 2
            visited[i][j] = 1

            println("curTime: $curTime, curOrange: <$i, $j>")
            myGrid.forEach{ row ->
                println("${row.toString()}")
            }

            
            // 4-adjacent
            for(k in 0 until 4){
                val adjI = i + dirI[k]
                val adjJ = j + dirJ[k]
                if(isInRange(adjI, adjJ)){
                    if((myGrid[adjI][adjJ] == 1)&&(visited[adjI][adjJ] == 0)){
                        q.addLast(Pair(Pair(adjI, adjJ), curTime+1))
                    }
                }
            }
        }
        
        // if fresh orange exists, return -1
        if(myGrid.flatten().contains(1)) return -1
        return rotTime
    }
}