连通块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int map1[3][3]={
    {1,1,0},
    {0,1,0},
    {1,0,1}
};
int temp=0;
bool flag=false;
void dfs(int x,int y) {
    if (x < 0 || x >=3 || y < 0 || y >= 3||map1[x][y]!=1) return;
    map1[x][y]=0;
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y+1);
    dfs(x,y-1);
}
int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (map1[i][j] == 1) {
                temp++;
                dfs(i,j);
            }
        }
    }
        cout<<temp;
    return 0;
}

输出连通块面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
int map1[4][4]={
    {1,0,1,0},
    {1,1,0,0},
    {0,0,1,1},
    {0,0,1,0}
};
int dfs(int x,int y) {
    if (x>3||y>3||x<0||y<0||map1[x][y]==0)return 0;
    return map1[x][y]=0,dfs(x+1,y)+dfs(x-1,y)+dfs(x,y+1)+dfs(x,y-1)+1;
}
int a=0,b=0;
int main() {
    for(int i=0;i<4;i++) {
        for(int j=0;j<4;j++) {
            if (map1[i][j]==1) {
                a=dfs(i,j);
                b=max(a,b);
            }
        }
    }
    cout<<b;
    return 0;
}

路径数量问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int a[3][3] = {
    {1,1,1},
    {1,1,1},
    {1,1,1}
};
bool vis[3][3];
int dfs(int x,int y) {
    if (x>=3||x<0||y>=3||y<0||vis[x][y]==true||a[x][y]==0) return 0;
    if (x==2&&y==2) return 1;
    vis[x][y] = true;
    int res = dfs(x+1,y)+dfs(x-1,y)+dfs(x,y+1)+dfs(x,y-1);
    vis[x][y] = false;
    return res;
}
int main() {
    cout<<dfs(0,0)<<endl;
    return 0;
}

① 是不是要求“最短”？

是 → BFS
不是 → 继续判断

② 是不是“只能单方向移动”？

是 → DP
不是 → 继续判断

③ 是否涉及“访问历史依赖”？

是 → DFS 回溯
不是 → DP 或 BFS

🧪 例题：最短步数(BFS)

给你一个 n×m 的地图：

  • 1 表示可以走
  • 0 表示障碍
  • 只能上下左右移动
  • 求从左上角 (0,0) 到右下角 (n-1,m-1) 的最短步数

示例输入（3×3）

1
2
3
4
3 3
1 1 1
1 0 1
1 1 1

目标：输出最短步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[1005][1005];
int dista[1005][1005];
bool vis[1005][1005];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    queue<pair<int,int>> q;

    // 起点初始化
    q.push({0, 0});
    vis[0][0] = true;
    dista[0][0] = 0;

    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        // 如果到达终点
        if(x == n-1 && y == m-1) {
            cout << dista[x][y] << endl;
            return 0;
        }

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m
               && a[nx][ny] == 1 && !vis[nx][ny]) {

                vis[nx][ny] = true;
                dista[nx][ny] = dista[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    // 如果走不到终点
    cout << -1 << endl;
    return 0;
}