130. 被围绕的区域
解题思路：从边缘的'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 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 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 queue = new ArrayDeque();
Map 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 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);
}
}
}
200. 岛屿数量
/**
* Copyright (C), 2018-2020
* FileName: numIslands200
* Author: xjl
* Date: 2020/8/11 15:30
* Description: 岛屿的数量
*/
package DFS_BFS;
public class numIslands200 {
//保存行列的数值
int m;
int n;
// 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
int[] dx = new int[]{0, 0, 1, -1};
int[] dy = new int[]{1, -1, 0, 0};
// 标记数组，标记了 grid 的坐标对应的格子是否被访问过
private boolean[][] marked;
public int numIslands(char[][] grid) {
int result = 0;
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
m = grid.length;//行
n = grid[0].length;//列
//表示没有访问
marked = new boolean[m][n];
//开始遍历
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
//如果是遍历等于1表示的陆地
if (grid[i][j] == '1' && !marked[i][j]) {
dfs(grid, i, j);
//表示有一个陆地
result++;
} else {
continue;
}
}
}
return result;
}
public int numIslands1(char[][] grid) {
m = grid.length;
if (m == 0) {
return 0;
}
n = grid[0].length;
//赋值都是false
marked = new boolean[m][n];
//统计数量
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果是岛屿中的一个点，并且没有被访问过。就进行深度优先遍历
if (!marked[i][j] && grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
// 从坐标为 (i,j) 的点开始进行深度优先遍历
private void dfs(char[][] grid, int i, int j) {
//表示访问过了
marked[i][j] = true;
// 得到 4 个方向的坐标
for (int k = 0; k < 4; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
// 如果不越界、没有被访问过、并且还要是陆地
if (inArea(newX, newY) && grid[newX][newY] == '1' && !marked[newX][newY]) {
dfs(grid, newX, newY);
}
}
}
// 判断是否越界
private boolean inArea(int x, int y) {
// 等于号不要忘了
return x >= 0 && x < m && y >= 0 && y < n;
}
}
