Leetcode 994) Rotting Oranges

05 Aug 2021 in Algorithms

내 답안

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> q = new LinkedList<>();
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==2){
                    q.add(new int[]{i,j});
                }
            }
        }
        int cnt=0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0;i<size;i++ ){
                int[] ind = q.poll();
                if( ind[0]+1<grid.length && grid[ind[0]+1][ind[1]]==1){
                    grid[ind[0]+1][ind[1]]=2;
                    q.add(new int[] {ind[0]+1,ind[1]});
                }
                if(ind[0]-1>=0  && grid[ind[0]-1][ind[1]]==1){
                    grid[ind[0]-1][ind[1]]=2;
                    q.add(new int[] {ind[0]-1,ind[1]});

                }
                if( ind[1]+1<grid[0].length && grid[ind[0]][ind[1]+1]==1){
                    grid[ind[0]][ind[1]+1]=2;
                    q.add(new int[] {ind[0],ind[1]+1});

                }
                if(ind[1]-1>=0 && grid[ind[0]][ind[1]-1]==1){
                    grid[ind[0]][ind[1]-1]=2;
                    q.add(new int[]{ind[0],ind[1]-1});
                }
            }
            if(q.size()!=0){
                cnt++;
            }
        }

        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    return -1;
                }
            }
        }
        return cnt;
    }
}

다른 답안

class Solution {
    // run the rotting process, by marking the rotten oranges with the timestamp
    public boolean runRottingProcess(int timestamp, int[][] grid, int ROWS, int COLS) {
        int[][] directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        // flag to indicate if the rotting process should be continued
        boolean toBeContinued = false;
        for (int row = 0; row < ROWS; ++row)
            for (int col = 0; col < COLS; ++col)
                if (grid[row][col] == timestamp)
                    // current contaminated cell
                    for (int[] d : directions) {
                        int nRow = row + d[0], nCol = col + d[1];
                        if (nRow >= 0 && nRow < ROWS && nCol >= 0 && nCol < COLS)
                            if (grid[nRow][nCol] == 1) {
                                // this fresh orange would be contaminated next
                                grid[nRow][nCol] = timestamp + 1;
                                toBeContinued = true;
                            }
                    }
        return toBeContinued;
    }

    public int orangesRotting(int[][] grid) {
        int ROWS = grid.length, COLS = grid[0].length;
        int timestamp = 2;
        while (runRottingProcess(timestamp, grid, ROWS, COLS))
            timestamp++;

        // end of process, to check if there are still fresh oranges left
        for (int[] row : grid)
            for (int cell : row)
                // still got a fresh orange left
                if (cell == 1)
                    return -1;


        // return elapsed minutes if no fresh orange left
        return timestamp - 2;
    }
}