Rotten oranges

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

The value 0 represents an empty cell; Value 1 represents fresh oranges; A value of 2 represents rotten oranges. Every minute, any fresh orange next to a rotten orange (four squares up) will rot.

Returns the minimum number of minutes that must pass until there are no fresh oranges in the cell. If that is not possible, return -1.Source: LeetCode

Links:Leetcode-cn.com/problems/ro…

Copyright belongs to the Collar buckle network.

Diagram ideas

See this kind of circle to spread out of the topic, immediately think of breadth-first search algorithm!

So what is a generalized first algorithm

As shown below, search by layer is a broad-first algorithm; Start from one or more points and spread out to search;

Broad priority algorithm basic routine is what

Please remember the following formula! See wide type priority search directly to set!

forQueue. Add (start);while(! queue.isEmpty()){int[] start = queue.poll(); // Take out the starting point
    forIterate over all the children of start againifCheck whether the node is valid and not accessed queue.add(child node); }Copy the code

Rotten orange solution

public int orangesRotting(int[][] grid) {
    int[][] dir = new int[] [] {{1.0}, {-1.0}, {0, -1}, {0.1}};
    int x = grid.length,y = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int gridNum = 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            // Add all rotten oranges to the queue
            if(grid[i][j] == 2){
                queue.add(new int[]{i, j,0});
            }
            // Record all oranges that are not rotten
            if(grid[i][j] == 1){ gridNum++; }}}int num = 0;
    while(! queue.isEmpty()){int[] xy = queue.poll();
        int mx = xy[0],my = xy[1],time = xy[2];
        // Take an orange out of the queue and traverse its four sides
        for (int i = 0; i < 4; i++) {
            int x_ = mx + dir[i][0],y_ = my+dir[i][1];
            // Set boundary conditions
            if(x_>=0 && y_>=0&& x_< x && y_<y && grid[x_][y_]! =2) {// Determine if the orange is rotten, if not, assume it is rotten to prevent a second calculation
                if(grid[mx][my] == 1){
                    queue.add(new int[]{mx, my,time+1});
                    grid[mx][my] = 2;
                    gridNum --;
                }
            }
        }
        num = time;
    }
    if(gridNum ! =0){
        num = -1;
    }
    return num;
}
Copy the code

Only routine is popular, this wave of routine you learn to waste?