一、二进制矩阵中的最短路径
bfs最短路径
思路：从 0, 0 这个点出发，将周围点入队，再从队中拿出这些点并将其周围点入队，也就是一圈圈的寻找
可以理解为一圈圈的话，每一圈就代表一步
-
注意点：不能重复访问单元格
- 开始：将 0, 0 入队，并标记被访问，第一步记录
- 符合遍历条件：不越界且等于0
- 然后入队
- 每次外循环确保队列不空
- 内循环，将开始循环前队列的元素个数记录下来
- 然后逐一出队，直到记录为0
- 出队后处理：将这个点的八个方向都确定是否可以入队：
- 不越界、未访问、值为0
- 入队、标记被访问
- 当这一圈的遍历中出现
(n - 1, n - 1)）这个点，那么路径已经可以确定是走完了，直接返回步数即可
class Solution { //更改八个方向的数组：右，右下，下，左下，左，左上，上，右上 private int[] X = {0,1,1,1,0,-1,-1,-1};//行 private int[] Y = {1,1,0,-1,-1,-1,0,1};//列 private int m,n; public int shortestPathBinaryMatrix(int[][] grid) { m = grid.length; n = grid[0].length; if(grid[0][0] == 1 || grid[m-1][n-1] == 1) return -1;//特殊情况特殊考虑，出口和入口被堵死 if(m == 1 && grid[0][0] == 0) return 1;//只有一个0的情况 int[][] memory = new int[m][n];//记忆数组，访问过的都记录一下 Queue<int[]> a = new LinkedList();//队列，里面保存int数组为坐标 a.add(new int[]{0, 0});//一开始将起点入队 memory[0][0] = 1;//起点标记为已经访问 int step = 1;//理论上的初值 while (!a.isEmpty()){ int s = a.size();//为step叠加用，用于将初始队列中的元素都取出来 for (int i = 0; i < s; i++){ int[] temp = a.poll();//poll()方法队首元素出队 int x = temp[0]; int y = temp[1]; for(int j = 0; j < 8; j++){ int x1 = x + X[j]; int y1 = y + Y[j]; if(x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && grid[x1][y1] == 0 && memory[x1][y1] != 1){//数组不越界，值为1，//没有被访问过才能入队 a.add(new int[]{x1, y1});//入队 memory[x1][y1] = 1;//标记已访问！！！！！！！！！！！！不要忘记 } } if(x == m-1 && y == n-1) return step;//终止条件 } step++; } return -1;//队列为空即为不能到达终点，返回-1 } }
二、被围绕的区域
class Solution { public void solve(char[][] board) { //判断字符‘o’是否处于边界或与边界的字符‘O’相连，判否：将这批字符‘O’填充为‘X’ for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { if(board[i][j] == 'O') { List<int[]> points = helper(i, j, board); if(points !=null) { while(!points.isEmpty()) { int[] t = points.remove(0); board[t[0]][t[1]] = 'X'; } } } } } } //上，下，左，右 private int[] xi = new int[] {-1,1,0,0}; private int[] yj = new int[] {0,0,-1,1}; private List<int[]> helper(int i, int j, char[][] board) { List<int[]> ans = new ArrayList<>(); int[][] memory = new int[board.length][board[0].length]; Queue<int[]> queue = new LinkedList<>(); queue.add(new int[] {i, j}); while(!queue.isEmpty()) { int size = queue.size(); while(size > 0) { size--; int[] t = queue.poll(); int ti = t[0]; int tj = t[1]; if(ti == 0 || ti == board.length - 1 || tj == 0 || tj == board[0].length - 1) { return null; } ans.add(t); memory[ti][tj] = 1; for(int k = 0; k < 4; k++) { int x = ti + xi[k]; int y = tj + yj[k]; if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && memory[x][y] == 0 && board[x][y] == 'O') { memory[x][y] = 1; queue.add(new int[] {x, y}); } } } } return ans; } }分析题目发现：被围绕的字符‘O'都不会到达矩阵的边界上，所以遇到该字符后，利用bfs搜索确定被围绕的区域，然后改为字符’X‘即可
但思路反着来：
遍历矩阵边界，将与边界相连的字符’O'都改为‘#’
然后，遍历矩阵，将剩余‘O'填充为’X‘，’#‘填充为’O‘
实际上比不需要记忆数组了，因为可以通过修改原数组做标记
class Solution { public void solve(char[][] board) { int rows = board.length, cols = board[0].length; // 从边界开始查找，转换 for (int i = 0; i < rows; ++i) {//先找左右两列 if (board[i][0] == 'O') bfs(board, i, 0); if (board[i][cols - 1] == 'O') bfs(board, i, cols - 1); } for (int i = 0; i < cols; ++i) {//找上下两行 if (board[0][i] == 'O') bfs(board, 0, i); if (board[rows - 1][i] == 'O') bfs(board, rows - 1, i); } // 恢复转换 和 按题意设置 X元素 for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (board[i][j] == 'O') board[i][j] = 'X'; if (board[i][j] == '#') board[i][j] = 'O'; } } } private void bfs(char[][] board, int i, int j) { int m = board.length, n = board[0].length; Queue<int[]> queue = new LinkedList(); queue.add(new int[] {i, j}); while(!queue.isEmpty()) { int[] t = queue.poll(); int ti = t[0]; int tj = t[1]; if(ti >= 0 && ti < m && tj >= 0 && tj < n && board[ti][tj] == 'O') { board[ti][tj] = '#'; queue.add(new int[] {ti - 1, tj}); queue.add(new int[] {ti + 1, tj}); queue.add(new int[] {ti, tj - 1}); queue.add(new int[] {ti, tj + 1}); } } } }
三、所有可能的路径
没看题的结果：
少看的条件：
找出所有从节点0到节点n-1的路径并输出误以为存在多个节点作为路径起点
考虑了如何多个起点的做法
class Solution { public List<List<Integer>> allPathsSourceTarget(int[][] graph) { int[] begin = new int[graph.length];//起点数组，为0的才可做为新起点 List<List<Integer>> ans = new ArrayList<>(); for(int i = 0; i < graph.length; i++) { if(begin[i] == 0) {//是起点 begin[i] = 1; List<Integer> road = new ArrayList<>(); road.add(i); for(int j = 0; j < graph[i].length; j++) { begin[graph[i][j]] = 1; findRoad(ans, graph, graph[i][j], road, begin); } } } return ans; } private void findRoad(List<List<Integer>> ans, int[][] graph, int index, List<Integer> road, int[] begin) { road = new ArrayList(road); road.add(index); if(graph[index].length == 0) { ans.add(road); } else { for(int k = 0; k < graph[index].length; k++) { begin[graph[index][k]] = 1; findRoad(ans, graph, graph[index][k], new ArrayList(road), begin); } } } }
-
正确的做法
从节点
0到节点n-1的路径：节点0，就是数组的第一行需要注意路径的添加与new
class Solution { //从节点 0 到节点 n-1 的路径 public List<List<Integer>> allPathsSourceTarget(int[][] graph) { List<List<Integer>> ans = new ArrayList<>(); if(graph.length > 0) {//需要第一行，节点0存在 //路径是从节点0开始的 List<Integer> road = new ArrayList<>(); road.add(0); //第一行，寻找路径的下一个点 for(int j = 0; j < graph[0].length; j++) { findRoad(ans, graph, graph[0][j], road); } } return ans; } private void findRoad(List<List<Integer>> ans, int[][] graph, int index, List<Integer> road) { //先存入当前行代表的节点 road = new ArrayList(road); road.add(index); //如果当前行是 n-1 个节点，那么不需要在这一行里确定下一个节点，因为这个节点已经是路径终点 if(index == graph.length - 1) { ans.add(road); } else {//除去最后一行都需要继续找下一个节点 for(int k = 0; k < graph[index].length; k++) { findRoad(ans, graph, graph[index][k], new ArrayList(road)); } } } }
