Leetcode
2020.04.14 03:12

994. Rotting Oranges

조회 수 132 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

 

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

 

Note:

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] is only 01, or 2.


class Point {
    int row;
    int col;
    public Point(int row, int col){
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Point> queue = new LinkedList<Point>();
        int rotting = -1;
        
        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                if(grid[row][col] == 2){
                    queue.add(new Point(row, col));
                }
            }
        }
        queue.add(null);
        
        boolean isNull = false;
        while(!queue.isEmpty()){
            Point p = queue.remove();
            if(p == null){
                if(isNull == false){
                    queue.add(null);
                    rotting++;
                }
                isNull = true;
            }else{
                if(p.row > 0 && grid[p.row-1][p.col] == 1){
                    queue.add(new Point(p.row-1, p.col));
                    grid[p.row-1][p.col] = 2;
                }
                if(p.col > 0 && grid[p.row][p.col-1] == 1){
                    queue.add(new Point(p.row, p.col-1));
                    grid[p.row][p.col-1] = 2;
                }
                if(p.row + 1 < grid.length && grid[p.row+1][p.col] == 1){
                    queue.add(new Point(p.row+1, p.col));
                    grid[p.row+1][p.col] = 2;
                }
                if(p.col + 1 < grid[0].length && grid[p.row][p.col+1] == 1){
                    queue.add(new Point(p.row, p.col+1));
                    grid[p.row][p.col+1] = 2;
                }
                isNull = false;
            }
        }
        
        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                if(grid[row][col] == 1){
                    rotting = -1;
                    break;
                }
            }
        }
        
        return rotting;
    }
    
}


class Point {
    int row;
    int col;
    public Point(int row, int col){
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Point> queue = new LinkedList<Point>();
        int rotting = -1;
        int total = 0;
        
        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                if(grid[row][col] == 2){
                    queue.add(new Point(row, col));
                }
                if(grid[row][col] == 1){
                    total++;
                }
            }
        }
        queue.add(null);
        
        boolean isNull = false;
        while(!queue.isEmpty()){
            Point p = queue.remove();
            if(p == null){
                if(isNull == false){
                    queue.add(null);
                    rotting++;
                }
                isNull = true;
            }else{
                if(p.row > 0 && grid[p.row-1][p.col] == 1){
                    queue.add(new Point(p.row-1, p.col));
                    grid[p.row-1][p.col] = 2;
                    total--;
                }
                if(p.col > 0 && grid[p.row][p.col-1] == 1){
                    queue.add(new Point(p.row, p.col-1));
                    grid[p.row][p.col-1] = 2;
                    total--;
                }
                if(p.row + 1 < grid.length && grid[p.row+1][p.col] == 1){
                    queue.add(new Point(p.row+1, p.col));
                    grid[p.row+1][p.col] = 2;
                    total--;
                }
                if(p.col + 1 < grid[0].length && grid[p.row][p.col+1] == 1){
                    queue.add(new Point(p.row, p.col+1));
                    grid[p.row][p.col+1] = 2;
                    total--;
                }
                isNull = false;
            }
        }

        if(total > 0){
            rotting = -1;
        }
        
        return rotting;
    }
}


class Point {
    int row;
    int col;
    public Point(int row, int col){
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Point> queue = new LinkedList<Point>();
        int rotting = 0;
        int total = 0;
        
        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                if(grid[row][col] == 2){
                    queue.offer(new Point(row, col));
                }
                if(grid[row][col] == 1){
                    total++;
                }
            }
        }
        
        while(queue.size() > 0){
            boolean isRotten = false;
            int loop = queue.size();
            for(int i=0; i<loop; i++){
                Point p = queue.poll();
            
                if(p.row > 0 && grid[p.row-1][p.col] == 1){
                    queue.offer(new Point(p.row-1, p.col));
                    grid[p.row-1][p.col] = 2;
                    isRotten = true;
                    total--;
                }
                if(p.col > 0 && grid[p.row][p.col-1] == 1){
                    queue.offer(new Point(p.row, p.col-1));
                    grid[p.row][p.col-1] = 2;
                    isRotten = true;
                    total--;
                }
                if(p.row + 1 < grid.length && grid[p.row+1][p.col] == 1){
                    queue.offer(new Point(p.row+1, p.col));
                    grid[p.row+1][p.col] = 2;
                    isRotten = true;
                    total--;
                }
                if(p.col + 1 < grid[0].length && grid[p.row][p.col+1] == 1){
                    queue.offer(new Point(p.row, p.col+1));
                    grid[p.row][p.col+1] = 2;
                    isRotten = true;
                    total--;
                }
            }
            if(isRotten == true){
                rotting++;
            }
        }
        
        if(total > 0){ //rest of 1's set
            rotting = -1;
        }
        
        return rotting;
    }
}


class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int rotting = 0;
        int total = 0;
        
        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                if(grid[row][col] == 2){
                    queue.offer(new int[]{row,col});
                }
                if(grid[row][col] == 1){
                    total++;
                }
            }
        }
        
        while(queue.size() > 0){
            boolean isRotten = false;
            int loop = queue.size();
            for(int i=0; i<loop; i++){
                int[] p = queue.poll();
            
                if(p[0] > 0 && grid[p[0]-1][p[1]] == 1){
                    queue.offer(new int[]{p[0]-1, p[1]});
                    grid[p[0]-1][p[1]] = 2;
                    isRotten = true;
                    total--;
                }
                if(p[1] > 0 && grid[p[0]][p[1]-1] == 1){
                    queue.offer(new int[]{p[0], p[1]-1});
                    grid[p[0]][p[1]-1] = 2;
                    isRotten = true;
                    total--;
                }
                if(p[0] + 1 < grid.length && grid[p[0]+1][p[1]] == 1){
                    queue.offer(new int[]{p[0]+1, p[1]});
                    grid[p[0]+1][p[1]] = 2;
                    isRotten = true;
                    total--;
                }
                if(p[1] + 1 < grid[0].length && grid[p[0]][p[1]+1] == 1){
                    queue.offer(new int[]{p[0], p[1]+1});
                    grid[p[0]][p[1]+1] = 2;
                    isRotten = true;
                    total--;
                }
            }
            if(isRotten == true){
                rotting++;
            }
        }
        
        if(total > 0){ //rest of 1's set
            rotting = -1;
        }
        
        return rotting;
    }
}


[문제] https://leetcode.com/problems/rotting-oranges/



?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
17 Leetcode 287. Find the Duplicate Number hooni 2020.04.16 146
16 Leetcode 253. Meeting Rooms II hooni 2020.04.15 121
15 Leetcode 731. My Calendar II hooni 2020.04.15 117
14 Leetcode 729. My Calendar I hooni 2020.04.15 121
13 Leetcode 692. Top K Frequent Words hooni 2020.04.15 110
12 Leetcode 973. K Closest Points to Origin hooni 2020.04.15 130
11 Leetcode 75. Sort Colors hooni 2020.04.14 118
10 Leetcode 2. Add Two Numbers hooni 2020.04.14 114
9 Leetcode 23. Merge k Sorted Lists hooni 2020.04.14 121
8 Leetcode 347. Top K Frequent Elements hooni 2020.04.14 119
» Leetcode 994. Rotting Oranges file hooni 2020.04.14 132
6 Leetcode 3. Longest Substring Without Repeating Characters hooni 2020.04.09 130
5 Leetcode 62. Unique Paths file hooni 2020.04.09 122
4 Leetcode 946. Validate Stack Sequences hooni 2020.04.08 124
3 Leetcode 114. Flatten Binary Tree to Linked List hooni 2020.04.06 134
2 Leetcode 430. Flatten a Multilevel Doubly Linked List file hooni 2020.04.06 123
1 Leetcode 1055. Shortest Way to Form String hooni 2020.04.06 156
Board Pagination Prev 1 2 3 4 Next
/ 4