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

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 (!pty()) {    //只要队列不为空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();//用于判断每次是否有橘子被污染了，若这轮没有橘子被污染，天数就不加1boolean 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;}