994.腐烂的橘子——入门广度搜索

• 广度搜索

  • 每到一个节点时，先遍历该节点能够到达的所有下一节点
  • 之后从下一层节点中的第一个节点开始，寻找它能到达的所有节点…直至结束

• 在代码中表示为进队列和出队列的操作

int n = 10, m = 10;                   //地图宽高
void BFS()
{
    queue que;              //用队列来保存路口
    int graph[n][m];          //地图
    int px[] = {-1, 0, 1, 0};   //移动方向的数组
    int py[] = {0, -1, 0, 1};
    que.push(起点入队);      //将起点入队
    while (!que.empty()) {    //只要队列不为空
        auto temp = que.pop();          //得到队列中的元素
        for (int i = 0; i != 4; ++i) {
            if(//可以走) {
                //标记当前格子
                //将当前状态入队列，等待下次提取
            }
        }
    } 
}

• 针对腐烂的橘子这题，也可以用广度搜索解决
• 最初有多个橘子腐烂，把它们全部入队

static class Orange{
        int x;
        int y;
        public Orange(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static int orangesRotting(int[][] grid) {
    	//两个数组组合起来完成下、右、上、左的移动
        int[] posx = {1, 0, -1, 0};
        int[] posy = new int[]{0, 1, 0, -1};
        int count = 0;
        int len1 = grid.length;
        int len2 = grid[0].length;

        Queue<Orange> queue = new LinkedList();
        //将数组腐烂的橘子全部入队
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                if(grid[i][j] == 2){
                    queue.offer(new Orange(i, j));
                }
            }
        }
        while(!queue.isEmpty()){
            //上一轮刚刚被污染的橘子的个数，用它们执行下一步的污染
            int size = queue.size();
            //用于判断每次是否有橘子被污染了，若这轮没有橘子被污染，天数就不加1
            boolean flag = false;
            //遍历每个刚被污染的橘子
            for(int i = 0; i < size; i++){
                Orange cur = queue.poll();
                //遍历当前腐烂橘子的四个方向
                for(int j = 0; j < 4; j++){
                    if(cur.x + posx[j] < 0 || 
                    cur.x + posx[j] >= len1 ||
                    cur.y + posy[j] < 0 || 
                    cur.y + posy[j] >= len2 ||
                    grid[cur.x + posx[j]][cur.y + posy[j]] != 1)			
                    {
                        continue;
                    }
                    //有可以被污染的橘子
                    flag = true;
                    grid[cur.x + posx[j]][cur.y + posy[j]] = 2;
                    queue.offer(new Orange(cur.x + posx[j], cur.y + posy[j]));
                }
            }
            if(flag){
                count ++;
            }
        }
        //判断是否存在还没被污染的橘子
        boolean done = true;
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                if(grid[i][j] == 1){
                    done = false;
                    return -1;
                }
            }
        }
        return count;
    }