leetcode994腐烂的橘子

leetcode994 腐烂的橘子

题目描述

题目解析

深度优先遍历问题，需要利用队列来存取需要遍历的节点，同时为了维护遍历深度，需要维护一个字典来存取遍历深度

public int orangesRotting(int[][] grid){int[] dr = {-1, 1, 0, 0};int[] dc = {0, 0, -1, 1};int R = grid.length;int C = grid[0].length;int ans = 0;Queue<Integer> queue = new ArrayDeque<Integer>();Map<Integer, Integer> map = new HashMap<Integer, Integer>();for(int r = 0; r < R; r ++){for(int c = 0; c < C; c ++){// 把所有腐烂的橘子装入队列if(grid[r][c] == 2){int ucode = r * C + c;   //给每一个腐烂橘子节点进行编码 为 r * C + Rqueue.add(ucode);map.put(ucode, 0);}}}while(! queue.isEmpty()){int ucode = queue.remove();int r = ucode / C;  // 从编码中恢复其行号和列号int c = ucode % C;for(int k = 0; k < 4; k ++){    //遍历其上下左右节点int nbR = r + dr[k];int nbC = c + dc[k];// 找到邻近的没有腐烂的橘子if(nbR >= 0 && nbR < R && nbC >= 0 && nbC < C && grid[nbR][nbC] == 1){grid[nbR][nbC] = 2; //将未腐烂橘子变成腐烂橘子int code = nbR * C + nbC;queue.add(code); //将刚被腐烂的橘子压入队列map.put(code, map.get(ucode) + 1); // 设置橘子的腐烂时间为传播腐烂橘子的时间加1ans = map.get(code);}}}// 查询是否仍然有未腐烂的橘子，若有则表示存在橘子不能被腐烂，返回-1for(int[] row : grid)for(int num : row)if(num == 1)return -1;return ans;}