【优选算法】（第四十一篇）

目录

被围绕的区域（medium）

题目解析

讲解算法原理

编写代码

迷宫中离⼊⼝最近的出⼝（medium）

题目解析

讲解算法原理

编写代码

被围绕的区域（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个mxn的矩阵board，由若⼲字符'X'和'O'，找到所有被'X'围绕的区域，并将这些区域⾥所有的'O'⽤'X'填充。
⽰例1：

输⼊：board=[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的'O'都不会被填充为'X'。任何不在边界上，或不与边界上的'O'相连的'O'最终都会被填充为'X'。如果两个元素在⽔平或垂直⽅向相邻，则称它们是“相连”的。
⽰例2：

输⼊：board=[["X"]]

输出：[["X"]]
提⽰：
m==board.length
n==board[i].length
1<=m,n<=200
board[i][j]为'X'或'O'

讲解算法原理

解法：
算法思路：
正难则反。
可以先利⽤ bfs 将与边缘相连的 '0' 区域做上标记，然后重新遍历矩阵，将没有标记过的 '0' 修改成 'X' 即可。

编写代码

c++算法代码：

class Solution
{
 int dx[4] = {0, 0, 1, -1};
 int dy[4] = {1, -1, 0, 0};
 int m, n;
public:
 void solve(vector<vector<char>>& board) 
 {
 m = board.size(), n = board[0].size();
 // 1. 先处理边界上的 'O' 联通块，全部修改成 '.'
 for(int j = 0; j < n; j++)
 {
 if(board[0][j] == 'O') bfs(board, 0, j);
 if(board[m - 1][j] == 'O') bfs(board, m - 1, j);
 }
 for(int i = 0; i < m; i++)
 {
 if(board[i][0] == 'O') bfs(board, i, 0);
 if(board[i][n - 1] == 'O') bfs(board, i, n - 1);
 }
 // 2. 还原
 for(int i = 0; i < m; i++)
 for(int j = 0; j < n; j++)
 if(board[i][j] == 'O') board[i][j] = 'X';
 else if(board[i][j] == '.') board[i][j] = 'O';
 }
 void bfs(vector<vector<char>>& board, int i, int j)
 {
 queue<pair<int, int>> q;
 q.push({i, j});
 board[i][j] = '.';
 while(q.size())
 {
 auto [a, b] = q.front();
 q.pop();
 for(int k = 0; k < 4; k++)
 {
 int x = a + dx[k], y = b + dy[k];
 if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
 {
 q.push({x, y});
 board[x][y] = '.';
 }
 }
 }
 }
};

java算法代码：

class Solution
{
 int[] dx = {0, 0, 1, -1};
 int[] dy = {1, -1, 0, 0};
 int m, n;
 public void solve(char[][] board) 
 {
 m = board.length; n = board[0].length;
 // 1. 先处理边界的 'O' 联通块，全部修改成 '.'
 for(int j = 0; j < n; j++)
 {
 if(board[0][j] == 'O') bfs(board, 0, j);
 if(board[m - 1][j] == 'O') bfs(board, m - 1, j);
 }
 for(int i = 0; i < m; i++)
 {
 if(board[i][0] == 'O') bfs(board, i, 0);
 if(board[i][n - 1] == 'O') bfs(board, i, n - 1);
 }
 // 2. 还原
 for(int i = 0; i < m; i++)
 for(int j = 0; j < n; j++)
 if(board[i][j] == 'O') board[i][j] = 'X';
 else if(board[i][j] == '.') board[i][j] = 'O';
 }
 public void bfs(char[][] board, int i, int j)
 {
 Queue<int[]> q = new LinkedList<>();
 q.add(new int[]{i, j});
 board[i][j] = '.';
 while(!q.isEmpty())
 {
 int[] t = q.poll();
 int a = t[0], b = t[1];
 for(int k = 0; k < 4; k++)
 {
 int x = a + dx[k], y = b + dy[k];
 if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
 {
 board[x][y] = '.';
 q.add(new int[]{x, y});
 }
 }
 }
 }
}

迷宫中离⼊⼝最近的出⼝（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个mxn的迷宫矩阵maze（下标从0开始），矩阵中有空格⼦（⽤'.'表⽰）和墙（⽤'+'表⽰）。同时给你迷宫的⼊⼝entrance，⽤entrance=[entrancerow,entrancecol]表⽰你⼀开始所在格⼦的⾏和列。
每⼀步操作，你可以往上，下，左或者右移动⼀个格⼦。你不能进⼊墙所在的格⼦，你也不能离开迷宫。你的⽬标是找到离entrance最近的出⼝。出⼝的含义是maze边界上的空格⼦。
entrance格⼦不算出⼝。请你返回从entrance到最近出⼝的最短路径的步数，如果不存在这样的路径，请你返回-1。
⽰例1：

输⼊：maze=[["+","+",".","+"],[".",".",".","+"],["+","+","+","."]],entrance=[1,2]

输出：1
解释：
总共有3个出⼝，分别位于(1,0)，(0,2)和(2,3)。⼀开始，你在⼊⼝格⼦(1,2)处。
◦ 你可以往左移动2步到达(1,0)。◦ 你可以往上移动1步到达(0,2)。从⼊⼝处没法到达(2,3)。
所以，最近的出⼝是(0,2)，距离为1步。

⽰例2：

输⼊：maze=[["+","+","+"],[".",".","."],["+","+","+"]],entrance=[1,0]

输出：2
解释：
迷宫中只有1个出⼝，在(1,2)处。(1,0)不算出⼝，因为它是⼊⼝格⼦。初始时，你在⼊⼝与格⼦(1,0)处。◦ 你可以往右移动2步到达(1,2)处。所以，最近的出⼝为(1,2)，距离为2步。
⽰例3：

输⼊：maze=[[".","+"]],entrance=[0,0]
输出：-1
解释：
这个迷宫中没有出⼝。

提⽰：
maze.length==m
maze[i].length==n
1<=m,n<=100
maze[i][j]要么是'.'，要么是'+'。
entrance.length==2
0<=entrancerow<m
0<=entrancecol<n
entrance⼀定是空格⼦。

讲解算法原理

解法（bfs求最短路）：
算法思路：
利⽤层序遍历来解决迷宫问题，是最经典的做法。
我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候，得到起点到出⼝的最短距离。

编写代码

c++算法代码：

class Solution
{
 int dx[4] = {0, 0, 1, -1};
 int dy[4] = {1, -1, 0, 0};
public:
 int nearestExit(vector<vector<char>>& maze, vector<int>& e) 
 {
 int m = maze.size(), n = maze[0].size();
 bool vis[m][n];
 memset(vis, 0, sizeof vis);
 queue<pair<int, int>> q;
 q.push({e[0], e[1]});
 vis[e[0]][e[1]] = true;
 int step = 0;
 while(q.size())
 {
 step++;
 int sz = q.size();
 for(int i = 0; i < sz; i++)
 {
 auto [a, b] = q.front();
 q.pop();
 for(int j = 0; j < 4; j++)
 {
 int x = a + dx[j], y = b + dy[j];
 if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.'
&& !vis[x][y])
 {
 // 判断是否已经到达出⼝
 if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return
 step;
 q.push({x, y});
 vis[x][y] = true;
 }
 }
 }
 }
 return -1;
 }
};

java算法代码：

class Solution
{
 int[] dx = {0, 0, -1, 1};
 int[] dy = {1, -1, 0, 0};
 public int nearestExit(char[][] maze, int[] e) 
 {
 int m = maze.length, n = maze[0].length;
 boolean[][] vis = new boolean[m][n];
 Queue<int[]> q = new LinkedList<>();
 q.add(new int[]{e[0], e[1]});
 vis[e[0]][e[1]] = true;
 int step = 0;
 while(!q.isEmpty())
 {
 step++;
 int sz = q.size();
 for(int i = 0; i < sz; i++)
 {
 int[] t = q.poll();
 int a = t[0], b = t[1];
 for(int j = 0; j < 4; j++)
 {
 int x = a + dx[j], y = b + dy[j];
 if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.'
&& !vis[x][y])
 {
 // 判断是否已经到出⼝
 if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return
 step;
 vis[x][y] = true;
 q.add(new int[]{x, y});
 }
 }
 }
 }
 return -1;
 }
}