130. 被围绕的区域
DFS
解题思路
从边缘的'O'出发，用dfs将所有与边缘相邻的'O'改成'A'，未与边缘相邻的'O'将不会改变，然后遍历矩阵，将所有的'A'改成'O'，所有的'O'改成'X'。
/*** Copyright (C), 2018-2020* FileName: solve130* Author: xjl* Date: 2020/8/11 10:33* Description: 130. 被围绕的区域*/
package DP;public class solve130 {int M, N;/*** 使用的是的一个逆向思维** @param board*/public void solve1(char[][] board) {//如果说这个不存在的话if (board == null || board.length == 0) {return;}//求解的行列M = board.length;N = board[0].length;//开始从四标寻找 上下行for (int i = 0; i < M; i++) {if (board[i][0] == 'O')dfs(board, i, 0);if (board[i][N - 1] == 'O')dfs(board, i, N - 1);}//左右列for (int j = 0; j < N; j++) {if (board[0][j] == 'O')dfs(board, 0, j);if (board[M - 1][j] == 'O')dfs(board, M - 1, j);}//做个一个遍历for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {board[i][j] = board[i][j] == 'A' ? 'O' : 'x';}}}private void dfs(char[][] board, int x, int y) {if (x < 0 || x >= M || y < 0 || y >= N || board[x][y] != 'O') {return;}board[x][y] = 'A';//四个方向dfs(board, x + 1, y);dfs(board, x - 1, y);dfs(board, x, y + 1);dfs(board, x, y - 1);}
}
class Solution {int[][] d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int m;int n;public void solve(char[][] board) {m = board.length;if(m == 0)return;n = board[0].length;// 从上下左右四个边缘出发for(int i = 0; i < n; i++){dfs(board, 0, i);dfs(board, m-1, i);}for(int i = 0; i < m; i++){dfs(board, i, 0);dfs(board, i, n-1);}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'A')board[i][j] = 'O';else if(board[i][j] == 'O')board[i][j] = 'X';}}}private void dfs(char[][] board, int x, int y){if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')return ;board[x][y] = 'A';for(int i = 0; i < 4; i++)dfs(board, x + d[i][0], y + d[i][1]);}
}
/*** 采用的是的BFS的一个处理 常用的才做就是的队列的辅助* @param board*/public void solve2(char[][] board) {m = board.length;if(m == 0)return;n = board[0].length;Deque<int[]> queue = new LinkedList<>();for(int i = 0; i < n; i++){if(board[0][i] == 'O')queue.add(new int[]{0, i});if(board[m-1][i] == 'O')queue.add(new int[]{m-1, i});}for(int i = 1; i < m-1; i++){if(board[i][0] == 'O')queue.add(new int[]{i, 0});if(board[i][n-1] == 'O')queue.add(new int[]{i, n-1});}//BFS的关键while(!queue.isEmpty()){//取出一个来int[] t = queue.remove();board[t[0]][t[1]] = 'A';for(int i = 0; i < 4; i++){int x = t[0] + d[i][0];int y = t[1] + d[i][1];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){//添加下一个节点queue.add(new int[]{x, y});}}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'A')board[i][j] = 'O';else if(board[i][j] == 'O')board[i][j] = 'X';}}}
994. 腐烂的橘子（BFS+DFS）
/*** Copyright (C), 2018-2020* FileName: orangesRotting994* Author: xjl* Date: 2020/8/11 14:33* Description: 994. 腐烂的橘子*/
package DP;import java.util.*;public class orangesRotting994 {public int orangesRotting(int[][] grid) {Queue<Integer> queue = new LinkedList();int M = grid.length;//行int N = grid[0].length;//列//判断是否有腐烂的橘子boolean hasrottn = false;for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {//判断将有腐败橘子的放入队列中if (grid[i][j] == 2) {queue.add(i * N + j);//表示有的烂橘子hasrottn = true;}}}//用于控制坐标的int[] dx = new int[]{0, 0, 1, -1};int[] dy = new int[]{1, -1, 0, 0};int min = 0;while (!queue.isEmpty()) {//统计多少的长度int len = queue.size();//有多少的全部踢出来for (int i = 0; i < len; i++) {int curr = queue.remove();int x = curr / N;int y = curr % N;//去腐烂四周的for (int k = 0; k < 4; k++) {int xx = x + dx[k];int yy = y + dy[k];//判断是否越界 不能让新的值越界if (xx >= 0 && xx < M && yy < N && yy >= 0 && grid[xx][yy] == 1) {//感染橘子grid[xx][yy] = 2;queue.add(xx * N + yy);}}}min++;}//检测是否还有新鲜的橘子在里面 如果有的化那么不能完成任务for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) {return -1;}}}return hasrottn ? min - 1 : 0;}int[] dr = new int[]{-1, 0, 1, 0};int[] dc = new int[]{0, -1, 0, 1};/*** 多源广度优先搜索** @param grid* @return*/public int orangesRotting1(int[][] grid) {int R = grid.length, C = grid[0].length;Queue<Integer> queue = new ArrayDeque();Map<Integer, Integer> depth = new HashMap();for (int r = 0; r < R; ++r)for (int c = 0; c < C; ++c)if (grid[r][c] == 2) {int code = r * C + c;queue.add(code);depth.put(code, 0);}int ans = 0;while (!queue.isEmpty()) {int code = queue.remove();int r = code / C, c = code % C;for (int k = 0; k < 4; ++k) {int nr = r + dr[k];int nc = c + dc[k];if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {//腐烂grid[nr][nc] = 2;int ncode = nr * C + nc;queue.add(ncode);depth.put(ncode, depth.get(code) + 1);ans = depth.get(ncode);}}}//检测是否还有新鲜的橘子在里面 如果有的化那么不能完成任务for (int[] row : grid)for (int v : row)if (v == 1)return -1;return ans;}int grid[][];int r;int l;public int orangesRotting2(int[][] grid) {if (grid.length == 0)return -1;this.r = grid.length;this.l = grid[0].length;this.grid = grid;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 2) { //烂橘子开始传染病毒dps(i, j, 2);}}}int max = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1)return -1; //有新鲜的橘子max = Math.max(grid[i][j], max); //找到需要最多时间腐烂的橘子}}return max > 0 ? max - 2 : max;}public void dps(int i, int j, int val) {//表示的四烂橘子grid[i][j] = val;//判断周围是新鲜的橘子或者是烂得更慢的橘子if (i > 0 && (grid[i - 1][j] == 1 || grid[i - 1][j] - grid[i][j] > 1)) {dps(i - 1, j, 1 + val);}if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] - grid[i][j] > 1)) {dps(i, j - 1, 1 + val);}if (i < r - 1 && (grid[i + 1][j] == 1 || grid[i + 1][j] - grid[i][j] > 1)) {dps(i + 1, j, 1 + val);}if (j < l - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] - grid[i][j] > 1)) {dps(i, j + 1, 1 + val);}}
}