2025.10.9 17:26 开新坑 😃
# 网格图DFS
适用于需要计算连通块个数、大小以及对连通块的操作的题目,反正其关键词在于 连通块
网格图的遍历顺序图怎么画???
# 模板
完整模板
int m=grid.size(),n=grid[0].size();
int dirs[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
function<void(int,int)> dfs=[&](int x,int y){
if(x<0||y<0||x>=m||y>=n||) return ;//越界或者该点已经访问过了,返回
grid[x][y]= ;//将该点标记为访问过了
for(auto [dx,dy]:dirs){
int nx=x+dx,ny=y+dy;
dfs(nx,ny);
}
};
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dfs(i,j);
}
}
function<void(int,int)> dfs=[&](int x,int y){
if(grid[x][y]==0) return ;//如果该点已经访问,则
ans=max(ans,y);
for(auto [dx,dy]:dirs){
int nx=x+dx,ny=y+dy;
if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]>grid[x][y]) dfs(nx,ny);
}
grid[x][y]=0;//将该点标记为访问过了
};需要考虑 什么时候继续dfs? 如何判断重复访问? 对越界的判断.有何作用
哥伦布插旗子,每当遇到一个岛的时候,就用dfs将其完全标记插满旗子
此时由于每个节点最多被 访问一次,(被标记的地方不会进入函数)\
int DIRS[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下
dfs_target=[&](int i,int j){//利用dfs对该岛屿进行标记
if(i<0||i>=n||j<0||j>=m||grid[i][j]!='1'){
return 0;//越界或当前是水
}
int area=1;
grid[i][j]=1;
for (auto [dx, dy] : DIRS) {
area += dfs_target(x+dx, y+dy);
}
return area;
};
for(){
for(){
dfs_target;//遇到新岛,将其标记
ans++;
}
}dfs=[&](int i,int j){
if(i<0||i>=m||j<0||j>=n||grid[i][j]==0) return ;
cur=(cur+=grid[i][j])%k;
grid[i][j]=0;
for(auto [dx,dy] : DIRS){
dfs(i+dx,j+dy);
}
};# 边界问题
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col,int color) {
// 如果邻居越界或颜色不同，当前点是边界
int m = grid.size(), n = grid[0].size(), start = grid[row][col];
vector<vector<bool>> visited(m, vector<bool>(n, false));
int dirs[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
vector<pair<int, int>> borders;
if (color == start)
return grid;
function<void(int, int)> dfs = [&](int x, int y) {
if (visited[x][y]) return;
visited[x][y] = true;
bool isBorder = false;
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
isBorder = true;
} else if (grid[nx][ny] != start) {
isBorder = true;
} else {
dfs(nx, ny);
}
}
if (isBorder) {
borders.emplace_back(x, y);
}
};
dfs(row, col);
for (auto [x, y] : borders) {
grid[x][y] = color;
}
return grid;
}
};# 逆向思维
逆向思维,要找到被围绕的区域,不妨先找到含边界的区域.
在边界上找到的区域,其一定有边界,hhhhh
for(int i=0;i<m;i++){
if(grid[i][0]==1) dfs(i,0);
if(grid[i][n-1]==1) dfs(i,n-1);
}
for(int j=0;j<n;j++){
if(grid[0][j]==1) dfs(0,j);
if(grid[m-1][j]==1) dfs(m-1,j);
}
对于130,可以先将所有边界上的区域标记为 # ,此后 仅被包围区域有0,然后再次遍历,将0改为x,#恢复为0
对于1020,先将边界区域改为0,而后再次遍历统计剩余1的数量即可dfs/dp 都可以
1. 动态规划
下标含义: dp[i][j]从ij位置的最大移动次数
初始化:最后一列一定为0,因为无法再移动
递推公式: dp[i][j]=max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])+1;
遍历顺序 因为只要知道后面一列的所有值,就能判断当前列的值,所以是从右往左,每次遍历一列
2. dfs 但优化
//对于已经访问过的点,其已经进行了dfs更新了最佳答案,没必要再次访问
function<void(int, int)> dfs = [&](int i, int j) {
ans = max(ans, j);
if (ans == n - 1) return; // ans 已达到最大
// 向右上/右/右下走一步
for (int k = max(i - 1, 0); k < min(i + 2, m); k++) {
if (grid[k][j + 1] > grid[i][j]) {
dfs(k, j + 1);
}
}
grid[i][j] = 0;
};# 判断是否访问的问题
一般情况下,对于访问过的点,修改其数值就可以标记该点是否已经访问,如,访问过陆地后将其标记为水域, 但对于有些题目 ,有可能
原数组并不能随便修改,或者标记后跟没标记一样, 此时 就可以
eg.1765. 地图中的最高点 先将陆地都标记为-1,表示没访问过
1034. 边界着色 先将要修改的边界存起来,最后再修改
# 网格图BFS
DFS 是不撞南墙不回头；BFS 是先访问近的，再访问远的,故BFS一般用来解决最近路径问题
# 模板
模板
int m=grid.size(),n=grid[0].size(),ans=1;
queue<pair<int,int>> que;
que.push({0,0});
grid[0][0]=1;
while(!que.empty()){
int size=que.size();//保证只每次访问一层
for(int i=0;i<size;i++){
auto [x,y]=que.front();
que.pop();
if(x==n-1&&y==n-1) return ans;//找到出口了,返回答案
for(auto [dx,dy]:dirs){
int nx=x+dx,ny=y+dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&grid[nx][ny]==0){
//当前点未出界且确实要访问
grid[nx][ny]=1;//标记为已经访问,防止调头
que.push({nx,ny});
}
}
}
ans++;
} int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size(), n = maze[0].size();
int dirs[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 修正方向数组
queue<pair<int, int>> que;
que.push({entrance[0], entrance[1]});
maze[entrance[0]][entrance[1]] = '+'; // 入口标记为已访问
int steps = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
auto [x, y] = que.front();
que.pop();
// 检查是否到达出口（边界且不是入口）
if ((x == 0 || x == m - 1 || y == 0 || y == n - 1) &&
!(x == entrance[0] && y == entrance[1])) {
return steps;//到达边界且不为入口时说明找到了答案
}
for (auto [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
maze[nx][ny] == '.') {
maze[nx][ny] = '+'; // 将其标记为墙,否则会重复
que.push({nx, ny});
}
}
}
steps++;
}
return -1;
}# 多源BFS
从各个陆地出发bfs,曼哈顿距离恰好为当前bfs访问的层数
而且当前海洋点被访问时,dis恰好为其到陆地的最近距离(因为从陆地出发大家都是每次走一步,谁先到该海洋点谁就里它最近)
2025.10.19 下午16:20 网格图入门结束
