1、墙与门
题目连接
题目描述：
注意：
m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] 是 -1、0 或 231 - 1
解题思路：
核心在于用队列把只存门和空房间的位置，把墙排除在外。刚好门的值为0，这样拿出队列里的每一个元素，搜索它的上下左右位置有没有空房间，有的话更新空房间的最近门距离就是该元素的值+1，之后把空房间的位置也入队列，继续拿出队列的下一个元素去更新它周围空房间的值。
遍历数组，把所有门的下标入队列。
依次拿出队列的元素，检查该元素的上下左右位置是否有空房间，有的话空房间的值改为：刚从队列拿出元素的值 + 1，就是该位置空房间的最近的门距离，之后把空房间的下标也入队列。重复前面的动作直到队列为空。
完整代码：
class Solution { private: int around[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; public: void wallsAndGates(vector<vector<int>>& rooms) { queue<pair<int, int>> q; int m = rooms.size(); int n = rooms[0].size(); // 1、先把所有的门都入队列 for(int i=0; i<m; ++i) { for(int j=0; j<n; ++j) { if(rooms[i][j] == 0) { q.push(make_pair(i, j)); } } } // 2、依次拿出队列里的坐标，看看该位置的上下左右是否有空房间 // 如果有空房间，那么空房间的最近门距离就是该位置的值+1，完成后原来空房间的坐标入队列 while(!q.empty()) { pair<int, int> pr = q.front(); q.pop(); int row = pr.first; int col = pr.second; for(int i=0; i<4; ++i) { int newRow = row + around[i][0]; int newCol = col + around[i][1]; if(newRow<0 || newRow>=m || newCol<0 || newCol>=n || rooms[newRow][newCol] != INT_MAX) { continue; } rooms[newRow][newCol] = rooms[row][col] + 1; q.push(make_pair(newRow, newCol)); } } } };
性能分析：
时间复杂度：O(m*n)。
空间复杂度：O(m*n)。最坏情况全部都是门，全部入队列
2、图像渲染
图像渲染
题目描述：
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
示例：
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出:
[[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
注意：
image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
解题思路：
给定一个位置，记该位置颜色为curColor，把这个位置附近的所有这个curColor颜色的区域块染成newColor。典型的单路径BFS，注意搜索前要先把当前位置的颜色染成newColor。
完整代码：
class Solution { int distance[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { // 1、创建一个存储下标的队列，把（sr，sc）先入队列，从这里开始搜索 int curColor = image[sr][sc]; if(curColor == newColor) { return image; } int row = image.size(); int col = image[0].size(); queue<pair<int, int>> q; q.push(make_pair(sr, sc)); image[sr][sc] = newColor; // 2、BFS向上下左右搜索curColor while(!q.empty()) { pair<int, int> front = q.front(); q.pop(); int i = front.first; int j = front.second; for(int d = 0; d < 4; ++d) { int ni = i + distance[d][0]; int nj = j + distance[d][1]; if(ni>=0 && ni<row && nj>=0 && nj<col && image[ni][nj]==curColor) { q.push(make_pair(ni, nj)); image[ni][nj] = newColor; } } } // 3、最后返回图像 return image; } };
性能分析：
时间复杂度：O(n*m)。最坏情况这个矩阵颜色都是curColor。
空间复杂度：O(n*m)。队列的开销。
3、01 矩阵
题目连接
题目描述：
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
注意：
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1
mat 中至少有一个 0
解题思路：
多路径源的搜索问题，考虑创建一个超级0来作为搜索时的标识。一开始把原矩阵中所有值为0的下标入队列，然后BFS搜索。
完整代码：
class Solution { int constExr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { // 1、创建 // 最终返回的结果矩阵ret // 用来标志多路径源集合的矩阵super，一开始把mat中值为0的下标对应到super中标志为1 // bfs时用到的存储下标键值对的队列，一开始把所有值为0的下标入队列 int row = mat.size(); int col = mat[0].size(); vector<vector<int>> ret(row, vector<int>(col)); vector<vector<int>> super(row, vector<int>(col)); queue<pair<int, int>> q; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { if(mat[i][j] == 0) { q.push(make_pair(i, j)); super[i][j] = 1; } } } // 2、进行多路径的广度优先搜索 while(!q.empty()) { pair<int, int> front = q.front(); int i = front.first; int j = front.second; q.pop(); for(int d = 0; d < 4; ++d) { int ni = i+constExr[d][0]; int nj = j+constExr[d][1]; if(ni>=0 && ni<row && nj>=0 && nj<col && !super[ni][nj]) { q.push(make_pair(ni, nj)); ret[ni][nj] = ret[i][j] + 1; super[ni][nj] = 1; } } } // 返回结果矩阵ret return ret; } };
性能分析：
时间复杂度：O(n*m)。最坏情况遍历整个数组。
空间复杂度：O(n*m)。队列的开销。
4、岛屿数量
题目连接
题目描述：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
注意：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’
解题思路：
创建一个队列，遍历数组如果遇到岛屿的话ret加一，并把岛屿的值改为’0’和它的下标入队列，如果队列不为空就取出队列的元素，搜索该位置的上下左右是否还有其他岛屿，有的话也同样把岛屿的值改为’0’和它的下标入队列，直到最后队列为空就算排除一座岛屿。
完整代码：
class Solution { private: int around[4][2]= { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; public: int numIslands(vector<vector<char>>& grid) { int ret = 0; queue<pair<int, int>> q; int m = grid.size(); int n = grid[0].size(); // 1、遍历数组，遇到岛屿ret就加一 for(int i=0; i<m; ++i) { for(int j=0; j<n; ++j) { // 2、遇到岛屿ret就加一，把该岛屿下标入队列，并把其值置为'0' if(grid[i][j] == '1') { q.push(make_pair(i, j)); ++ret; // 搜索入栈岛屿的上下左右位置是否还有其他岛屿，有的话也入队列，把值置为'0' // 直到最后队列为空，就算排除了一座岛屿 while(!q.empty()) { int row = q.front().first; int col = q.front().second; grid[row][col] = '0'; q.pop(); for(int k=0; k<4 ;++k) { int newRow = row+around[k][0]; int newCol = col+around[k][1]; if(newRow<0 || newRow>=m || newCol<0 || newCol>=n || grid[newRow][newCol] != '1') { continue; } grid[newRow][newCol] = '0'; q.push(make_pair(newRow, newCol)); } } } } } return ret; } };
性能分析：
时间复杂度：O(m*n)。
空间复杂度：O(min(m, n))。最坏情况全部是岛屿，因为一次可以排除该位置的上下左右，所以最多队列一次性存储元素的长度为min(m, n)。
5、钥匙和房间
题目连接
题目描述：
解题思路：
最初，除 0 号房间外的其余所有房间都被锁住，我们从0号房间开始搜索，遍历每个房间中其他房间的钥匙，搜索过程中统计可以进入的房间数量并标记每个房间是否已经进入。
完整代码：
class Solution { public: bool canVisitAllRooms(vector<vector<int>>& rooms) { // 1、定义了三个对象 // q：用来进行BFS的存储房间下标的队列 // count：统计能进入房间的数量 // vis：标记每个房间是否有被进入过 queue<int> q; int count = 0; vector<bool> vis(rooms.size(), false); // 2、第0号房间先入队列进行BFS q.push(0); ++count; vis[0] = true; while(!q.empty()) { int front = q.front(); q.pop(); // 遍历当前房间中其他房间的钥匙 for(auto e : rooms[front]) { if(!vis[e]) { q.push(e); ++count; vis[e] = true; } } } // 3、最终返回记录的count是否等于总的房间数 return count == rooms.size(); } };
性能分析：
时间复杂度：O(n+m)。n为房间总数，m为所有房间中钥匙的总数。
空间复杂度：O(n)。队列和vis的开销。
6、机器人移动范围
题目连接
题目描述：
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
输入描述：
一行三个正整数由空格分开，分别代表行数m，列数n，和坐标数位之和的阈值k，0 < m <= 100, 0 < n <= 100, 0 < k <= 20。
输出描述：
一个正整数，代表该机器人能够到达的格子数量。
示例：
输入：
3 3 6
输出：
9
解题思路：
从(0, 0)开始向上下左右四个方向搜索，如果坐标合法、坐标数位之和不大于k，并且没有被访问过就把这个坐标入队列。
完整代码：
#include <queue> #include <utility> #include <vector> #include <iostream> using namespace std; // 判断当前格子能否进入 bool IsEnter(int m, int n, int k) { int sum = 0; while(m) { sum += m%10; m /= 10; } while(n) { sum += n%10; n /= 10; } return sum <= k; } int PathRange(vector<vector<bool>>& matrix, int k) { // 1、定义相关对象 // matrix：标记格子的访问情况 // count：统计机器人能够达到多少个格子 // q：进行BFS的存储坐标键值对的队列 int count = 0; queue<pair<int, int>> q; // 2、从坐标0,0的格子开始搜索 if(IsEnter(0, 0, k)) { matrix[0][0] = true; ++count; q.push(make_pair(0, 0)); } while(!q.empty()) { pair<int, int> front = q.front(); int m = front.first; int n = front.second; q.pop(); // 上下左右四个方向搜索 if(m-1>=0 && !matrix[m-1][n] && IsEnter(m-1, n, k)) { matrix[m-1][n] = true; ++count; q.push(make_pair(m-1, n)); } if(m+1<(int)matrix.size() && !matrix[m+1][n] && IsEnter(m+1, n, k)) { matrix[m+1][n] = true; ++count; q.push(make_pair(m+1, n)); } if(n-1>=0 && !matrix[m][n-1] && IsEnter(m, n-1, k)) { matrix[m][n-1] = true; ++count; q.push(make_pair(m, n-1)); } if(n+1<(int)matrix[0].size() && !matrix[m][n+1] && IsEnter(m, n+1, k)) { matrix[m][n+1] = true; ++count; q.push(make_pair(m, n+1)); } } // 3、count就是最终到达的格子数 return count; } int main() { int row = 0; int col = 0; int k = 0; cin>>row>>col>>k; vector<vector<bool>> matrix(row, vector<bool>(col, false)); cout<<PathRange(matrix, k)<<endl; return 0; }
性能分析：
时间复杂度：O(m*n)。最多每一个格子都能到达。
空间复杂度：O(m*n)。队列的开销。
