[AcWing算法刷题]:DFS+BFS迷宫模板

题目来源：

题库 - AcWing

目录

DFS和BFS模板题目：迷宫类

        机器人的运动范围

        字母

        迷宫

        红与黑

        棋盘问题

        马走日

        全球变暖

DFS综合类

        乘积最大（提高课）

        单词接龙（提高课）

        取石子游戏（dfs数学推理）

---

机器人的运动范围

 BFS：

1.  
   class Solution {
2.  
   public:
3.  
    
4.  
   int get_sum(pair<int, int> p) {
5.  
   int s = 0;
6.  
   while (p.first) {
7.  
   s = p.first % 10;
8.  
   p.first /= 10;
9.  
   }
10.  
    while (p.second) {
11.  
    s = p.second % 10;
12.  
    p.second /= 10;
13.  
    }
14.  
    return s;
15.  
    }
16.  
     
17.  
    int movingCount(int threshold, int rows, int cols)
18.  
    {
19.  
    if (!rows || !cols) return 0;
20.  
    queue<pair<int,int>> q;
21.  
    vector<vector<bool>> st(rows, vector<bool>(cols, false));
22.  
     
23.  
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
24.  
     
25.  
    int res = 0;
26.  
    q.push({0, 0});
27.  
    while (q.size()) {
28.  
    auto t = q.front();
29.  
    q.pop();
30.  
    if (st[t.first][t.second] || get_sum(t) > threshold) continue;
31.  
    res ;
32.  
    st[t.first][t.second] = true;
33.  
    for (int i = 0; i < 4; i ) {
34.  
    int x = t.first dx[i], y = t.second dy[i];
35.  
    if (x >= 0 && x < rows && y >= 0 && y < cols) q.push({x, y});
36.  
    }
37.  
    }
38.  
     
39.  
    return res;
40.  
    }
41.  
    };

---

DFS：

1.  
   class Solution {
2.  
   public:
3.  
   int k;
4.  
   int b,a;
5.  
   int f[52][52];
6.  
   int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
7.  
   int movingCount(int threshold, int rows, int cols)
8.  
   {
9.  
   memset(f,false,sizeof f);
10.  
    b=cols,a=rows;
11.  
     
12.  
    int res=0;
13.  
     
14.  
    k=threshold;
15.  
     
16.  
    return dfs(0,0);
17.  
    }
18.  
    int dfs(int y,int x)
19.  
    {
20.  
    if(x<0||x>=a||y<0||y>=b||f[y][x]) return 0;
21.  
     
22.  
    f[y][x]=true;
23.  
    int res=0;
24.  
    int x1=x,y1=y;
25.  
    while(x1)
26.  
    {
27.  
    res =(x1%10);
28.  
    x1/=10;
29.  
    }
30.  
    while(y1)
31.  
    {
32.  
    res =(y1%10);
33.  
    y1/=10;
34.  
    }
35.  
     
36.  
    if(res>k) return 0;
37.  
    int sum=0;
38.  
     
39.  
    for(int i=0;i<4;i )
40.  
    {
41.  
    int q=x dx[i],p=y dy[i];
42.  
    sum =dfs(p,q);
43.  
    }
44.  
     
45.  
     
46.  
    return sum 1;
47.  
    }
48.  
    };
49.  
     
50.  
    作者：dfbdberberb
51.  
    链接：https://www.acwing.com/solution/content/11722/
52.  
    来源：AcWing
53.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

乘积最大（较难）

 

1.  
   #include<iostream>
2.  
   #include<vector>
3.  
   #include<algorithm>
4.  
   using namespace std;
5.  
    
6.  
   int n, k, ans;
7.  
   string str;
8.  
   bool st[20];//标记数字是否出现过
9.  
   vector<int>num;//存放分割的数字
10.  
     
11.  
    int number(int l, int r)//求区间[l,r]的数字
12.  
    {
13.  
    int res = 0;
14.  
    for (int i = l; i <= r; i )
15.  
    res = res * 10 str[i] - '0';
16.  
    return res;
17.  
    }
18.  
     
19.  
    void dfs(int pos, int cnt)//枚举到的第几个空位，乘号的当前个数
20.  
    {
21.  
    if (cnt == k)//如果乘号个数==题目所给的乘号个数
22.  
    {
23.  
    int y = number(pos, n - 1);//求出分割k次以后，第k 1个数的大小
24.  
    num.push_back(y);//放入分割的数字中
25.  
    int tmp = 1;
26.  
    for (int i = 0; i < num.size(); i )//求乘积
27.  
    tmp *= num[i];
28.  
    // cout<<num[i]<<" ";
29.  
    // cout<<endl;
30.  
    ans = max(ans, tmp);//更新最大值
31.  
    num.pop_back();
32.  
    return;
33.  
    }
34.  
    for (int i = 0; i < n - 1; i )//枚举分割位置
35.  
    {
36.  
    if (!st[i] && pos <= i)//如果分割位置未出现过，向下搜索
37.  
    {
38.  
    int x = number(pos, i);
39.  
    num.push_back(x);
40.  
    st[i] = true;
41.  
    dfs(i 1, cnt 1);
42.  
    st[i] = false;
43.  
    num.pop_back();
44.  
    }
45.  
    }
46.  
    }
47.  
     
48.  
    int main()
49.  
    {
50.  
    cin >> n >> k;
51.  
    cin >> str;
52.  
    dfs(0, 0);
53.  
    cout << ans << endl;
54.  
    return 0;
55.  
    }

---

字母

 

 BFS：

需要额外开一个字母数组来哈希快速找到该字母是否之前已经走过

1.  
   #include<iostream>
2.  
   #include<string>
3.  
   #include<vector>
4.  
   #include<queue>
5.  
   #include<algorithm>
6.  
   #include<memory.h>
7.  
   #include<cstring>
8.  
   using namespace std;
9.  
    
10.  
    int n, m;
11.  
    const int N = 50;
12.  
    vector<string> V;
13.  
    int mp[26];
14.  
     
15.  
    struct STATE {
16.  
    int x, y;
17.  
    int mp[26];
18.  
    int step;
19.  
    };
20.  
     
21.  
    int ans = -1;
22.  
    int addx[4] = { 1,-1,0,0 };
23.  
    int addy[4] = { 0,0,-1,1 };
24.  
     
25.  
    void bfs()
26.  
    {
27.  
    queue<struct STATE> q;
28.  
    struct STATE s;
29.  
    memset(s.mp, 0, sizeof s.mp);
30.  
    s.mp[V[0][0] - 'A'] = 1;//标记
31.  
    s.step = 1;
32.  
    s.x = 0, s.y = 0;
33.  
     
34.  
    q.push(s);
35.  
    while (q.size())
36.  
    {
37.  
    auto t = q.front();
38.  
    q.pop();
39.  
    ans = max(ans, t.step);
40.  
     
41.  
    for (int i = 0; i < 4; i )
42.  
    {
43.  
    int newx = t.x addx[i];
44.  
    int newy = t.y addy[i];
45.  
     
46.  
    if (newx >= 0 && newx < n && newy >= 0 && newy < m)
47.  
    {
48.  
    int idx = V[newx][newy] - 'A';
49.  
    if (t.mp[idx] == 1) continue;
50.  
    struct STATE next;
51.  
    next.x = newx;
52.  
    next.y = newy;
53.  
    next.step = t.step 1;
54.  
    memcpy(next.mp, t.mp, sizeof t.mp);
55.  
    next.mp[idx] = 1;
56.  
     
57.  
    q.push(next);
58.  
    }
59.  
    }
60.  
    }
61.  
    }
62.  
     
63.  
    int main()
64.  
    {
65.  
    cin >> n >> m;
66.  
     
67.  
    for (int i = 0; i < n; i )
68.  
    {
69.  
    string s;
70.  
    cin >> s;
71.  
    V.push_back(s);
72.  
    }
73.  
     
74.  
    bfs();
75.  
    cout << ans << endl;
76.  
     
77.  
    return 0;
78.  
    }

---

DFS：

同样需要开一个字母数组，来判断该字母是否出现过

不同的地方在与DFS搜索迷宫具有对称性：标记（   ）搜索下一层（  ）取消标记

1.  
   #include<iostream>
2.  
   #include<string>
3.  
   #include<vector>
4.  
   #include<algorithm>
5.  
   using namespace std;
6.  
    
7.  
   int n, m;
8.  
   const int N = 50;
9.  
   vector<string> V;
10.  
    int mp[26];
11.  
    int ans = -1;
12.  
     
13.  
    int addx[] = { 1,-1,0,0 };
14.  
    int addy[] = { 0,0,-1,1 };
15.  
     
16.  
    void dfs(int x, int y, int step)
17.  
    {
18.  
    int idx = V[0][0] - 'A';
19.  
    mp[idx] = 1;
20.  
     
21.  
    for (int i = 0; i < 4; i )
22.  
    {
23.  
    int newx = x addx[i];
24.  
    int newy = y addy[i];
25.  
     
26.  
    if (newx >= 0 && newx < n && newy >= 0 && newy < m)
27.  
    {
28.  
    int idx = V[newx][newy] - 'A';
29.  
    if (mp[idx] == 1) continue;
30.  
    mp[idx] = 1;
31.  
    dfs(newx, newy, step 1);
32.  
    mp[idx] = 0;
33.  
    }
34.  
    }
35.  
    ans=max(ans,step);
36.  
    }
37.  
     
38.  
    int main()
39.  
    {
40.  
    cin >> n >> m;
41.  
     
42.  
    for (int i = 0; i < n; i )
43.  
    {
44.  
    string s;
45.  
    cin >> s;
46.  
    V.push_back(s);
47.  
    }
48.  
     
49.  
    dfs(0, 0, 1);
50.  
    cout << ans << endl;
51.  
     
52.  
    return 0;
53.  
    }

---

迷宫

 

 BFS：

1.  
   #include<iostream>
2.  
   #include<queue>
3.  
   #include<cstring>
4.  
   using namespace std;
5.  
    
6.  
   typedef pair<int, int> PII;
7.  
   const int N = 110;
8.  
   int n;
9.  
   char g[N][N];
10.  
    bool st[N][N];
11.  
    queue<PII> q;
12.  
    int startx, starty;
13.  
    int endx, endy;
14.  
     
15.  
    int dx[4] = { -1,0,1,0 };
16.  
    int dy[4] = { 0,1,0,-1 };
17.  
     
18.  
    void bfs()
19.  
    {
20.  
    q.push({ startx,starty });
21.  
    st[startx][starty]=true;
22.  
    while (q.size())
23.  
    {
24.  
    auto t = q.front();
25.  
    q.pop();
26.  
     
27.  
    for (int i = 0; i < 4; i )
28.  
    {
29.  
    int x = t.first dx[i];
30.  
    int y = t.second dy[i];
31.  
    if (x >= 0 && x < n && y>=0 && y < n && !st[x][y] && g[x][y] == '.')
32.  
    {
33.  
    st[x][y] = true;
34.  
    q.push({ x,y });
35.  
    }
36.  
    else continue;
37.  
    }
38.  
    }
39.  
    }
40.  
     
41.  
    int main()
42.  
    {
43.  
    int T;
44.  
    cin >> T;
45.  
    while (T--)
46.  
    {
47.  
    cin >> n;
48.  
    for (int i = 0; i < n; i ) cin >> g[i];
49.  
     
50.  
    cin >> startx >> starty;
51.  
    cin >> endx >> endy;
52.  
     
53.  
    bfs();
54.  
     
55.  
    if(g[startx][starty]=='#' || g[endx][endy]=='#' || !st[endx][endy])cout << "NO" << endl;
56.  
    else if (st[endx][endy]) cout << "YES" << endl;
57.  
     
58.  
     
59.  
    memset(st, false, sizeof st);
60.  
    }
61.  
     
62.  
    return 0;
63.  
    }

DFS：

1.  
   #include <cstring>
2.  
   #include <iostream>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 110;
8.  
    
9.  
   char g[N][N];
10.  
    bool st[N][N];
11.  
    int n;
12.  
    int l1, r1, l2, r2;
13.  
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
14.  
    bool dfs(int x, int y)
15.  
    {
16.  
    if(x == l2 && y == r2)return true;
17.  
    st[x][y] = true;
18.  
    for(int i = 0; i < 4; i )
19.  
    {
20.  
    int a = x dx[i], b = y dy[i];
21.  
    if(a < 0 || a >= n || b < 0 || b >= n)continue;
22.  
    if(g[a][b] == '#')continue;
23.  
    if(st[a][b])continue;
24.  
    if(dfs(a, b))return true;
25.  
    }
26.  
    return false;
27.  
    }
28.  
     
29.  
    int main()
30.  
    {
31.  
    int T;
32.  
    cin >> T;
33.  
    while(T --)
34.  
    {
35.  
    memset(st, false, sizeof st);
36.  
    cin >> n;
37.  
    for(int i = 0; i < n; i ) cin >> g[i];
38.  
    cin >> l1 >> r1 >> l2 >> r2;
39.  
    if(g[l1][r1] == '#' || g[l2][r2] == '#')
40.  
    {
41.  
    puts("NO");
42.  
    continue;
43.  
    }
44.  
    if(dfs(l1, r1))puts("YES");
45.  
    else puts("NO");
46.  
    }
47.  
    return 0;
48.  
    }

---

红与黑

 

 DFS：

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int N=25;
5.  
   char g[N][N];
6.  
   bool st[N][N];
7.  
   int n,m;
8.  
   int dx[4]={-1,0,1,0};
9.  
   int dy[4]={0,1,0,-1};
10.  
     
11.  
    int dfs(int x,int y)
12.  
    {
13.  
    int cnt=1;
14.  
    st[x][y]=true;
15.  
     
16.  
    for(int i=0;i<4;i )
17.  
    {
18.  
    int a=x dx[i];
19.  
    int b=y dy[i];
20.  
    if(a<0 || a>=n || b<0 || b>=m) continue;
21.  
    if(g[a][b]!='.') continue;
22.  
    if(st[a][b]) continue;
23.  
     
24.  
    cnt =dfs(a,b);
25.  
    }
26.  
    return cnt;
27.  
    }
28.  
     
29.  
    int main()
30.  
    {
31.  
    while (cin >> m >> n, n || m)
32.  
    {
33.  
    for (int i = 0; i < n; i ) cin >> g[i];
34.  
     
35.  
    int x, y;
36.  
    for(int i=0;i<n;i )
37.  
    for (int j = 0; j < m; j )
38.  
    {
39.  
    if (g[i][j] == '@')
40.  
    {
41.  
    x = i;
42.  
    y = j;
43.  
    }
44.  
    }
45.  
    memset(st, 0, sizeof st);
46.  
    cout << dfs(x, y) << endl;
47.  
    }
48.  
     
49.  
    return 0;
50.  
    }

---

棋盘问题

 

1.  
   //DFS
2.  
   //类似于八皇后的一道多了一些限制的题
3.  
    
4.  
   #include <cstdio>
5.  
   #include <iostream>
6.  
   #include <cstring>
7.  
    
8.  
   using namespace std;
9.  
    
10.  
    const int N = 20;
11.  
     
12.  
    char g[N][N]; //存储输入棋盘
13.  
    int ans; //存储答案
14.  
    int n, k;
15.  
    int m; //存储已近放入棋盘的棋子数
16.  
    bool line[N]; //存储当前列上有没有其他棋子
17.  
     
18.  
    void dfs(int x)
19.  
    {
20.  
    if(m == k) //当棋子放光的时候
21.  
    {
22.  
    ans ;
23.  
    return;
24.  
    }
25.  
     
26.  
    if(x == n) //防止越界
27.  
    return;
28.  
     
29.  
    dfs(x 1); //这个是关键，因为 k <= m，因此可能有行不用放棋子，所以我们要手动舍弃行，直接进入下一行
30.  
    for(int i = 0; i < n; i ) //爆搜
31.  
    if(!line[i] && g[x][i] == '#')
32.  
    {
33.  
    line[i] = true;
34.  
    m ; //记录放入的棋子数
35.  
    dfs(x 1);
36.  
    line[i] = false; //还原初始状态
37.  
    m--;
38.  
    }
39.  
     
40.  
     
41.  
    }
42.  
     
43.  
    int main()
44.  
    {
45.  
    while(scanf("%d%d", &n, &k) && n != -1 && k != -1)
46.  
    {
47.  
    ans = m = 0;
48.  
    for(int i = 0; i < n; i )
49.  
    for(int j = 0; j < n; j )
50.  
    cin >> g[i][j];
51.  
     
52.  
    dfs(0);
53.  
    cout << ans << endl;
54.  
    }
55.  
     
56.  
    return 0;
57.  
    }

---

取石子游戏

 

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   using namespace std;
4.  
    
5.  
   int n, m;
6.  
    
7.  
   void dfs(int a, int b, int step)
8.  
   {
9.  
   if (a % b == 0 || a / b >= 2)
10.  
    {
11.  
    if (step & 1)
12.  
    {
13.  
    cout << "win" << endl;
14.  
    return;
15.  
    }
16.  
    else
17.  
    {
18.  
    cout << "lose" << endl;
19.  
    return;
20.  
    }
21.  
    }
22.  
    dfs(b, a % b, step 1);
23.  
    }
24.  
     
25.  
    int main()
26.  
    {
27.  
    while (cin >> n >> m, n || m)
28.  
    {
29.  
    if (n < m) swap(n, m);
30.  
    if (n / m >= 2) cout << "win" << endl;
31.  
    else dfs(n, m, 1);
32.  
    }
33.  
     
34.  
    return 0;
35.  
    }

---

马走日

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int T,n,m,a,b,ans;
4.  
   int vis[20][20];
5.  
   int dx[8]={2,1,-1,-2,-2,-1,1,2};//方向数组
6.  
   int dy[8]={1,2,2,1,-1,-2,-2,-1};//方向数组
7.  
   void dfs(int x,int y,int step)//step记录当前走了几个格子
8.  
   {
9.  
   if(step==n*m){//已遍历完所有的格子
10.  
    ans ;//答案加一
11.  
    return;
12.  
    }
13.  
    for(int i=0;i<8;i ){
14.  
    int kx=x dx[i];
15.  
    int ky=y dy[i];
16.  
    if(kx>=0&&kx<n&&ky>=0&&ky<m&&vis[kx][ky]==0){//判断
17.  
    vis[kx][ky]=1;//标记
18.  
    dfs(kx,ky,step 1);
19.  
    vis[kx][ky]=0;//回溯
20.  
    }
21.  
    }
22.  
    }
23.  
    int main()
24.  
    {
25.  
    scanf("%d",&T);
26.  
    while(T--){//多组测试数据
27.  
    ans=0;//一定要记得清空数据
28.  
    memset(vis,0,sizeof(vis));
29.  
    scanf("%d %d %d %d",&n,&m,&a,&b);
30.  
    vis[a][b]=1;//标记起点
31.  
    dfs(a,b,1);
32.  
    printf("%d\n",ans);
33.  
    }
34.  
    return 0;
35.  
    }

---

单词接龙（提高课）

 

1.  
   #include <cstring>
2.  
   #include <iostream>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 21;
8.  
    
9.  
   int n;
10.  
    string word[N];
11.  
    int g[N][N];//代表编号i的可以被j拼接 如i：asd，j：sdf，拼接长度为最小值g[i][j] = 2，i从0开始记位
12.  
    int used[N];//编号为i的单词使用次数
13.  
    int ans;
14.  
     
15.  
    void dfs(string dragon, int last)
16.  
    {
17.  
    ans = max((int)dragon.size(), ans);//取最大值，dragon.size()为当前合并的长度
18.  
     
19.  
    used[last] ;//编号为last的单词被用次数 ；
20.  
     
21.  
    for (int i = 0; i < n; i )
22.  
    if (g[last][i] && used[i] < 2)//used[i]<2代表单词用次数不超过2
23.  
    dfs(dragon word[i].substr(g[last][i]), i); //编号为last的可以被i拼接现在尾巴为i号
24.  
     
25.  
    used[last]--;//恢复现场
26.  
    }
27.  
     
28.  
    int main() {
29.  
    cin >> n;
30.  
    for (int i = 0; i < n; i ) cin >> word[i];
31.  
    char start;
32.  
    cin >> start;//首字母
33.  
     
34.  
    for (int i = 0; i < n; i )//遍历得到各个g[i][j]
35.  
    for (int j = 0; j < n; j ) {
36.  
    string a = word[i], b = word[j];
37.  
    for (int k = 1; k < min(a.size(), b.size()); k )
38.  
    if (a.substr(a.size() - k, k) == b.substr(0, k)) {
39.  
    g[i][j] = k;
40.  
    break;
41.  
    }
42.  
    }
43.  
     
44.  
    for (int i = 0; i < n; i )//找到首字母为strat的单词开始做dfs，dfs中会自动找到最大值
45.  
    if (word[i][0] == start)
46.  
    dfs(word[i], i);//从word[i]开始遍历，i代表现在是第几个单词
47.  
     
48.  
    cout << ans << endl;
49.  
     
50.  
    return 0;
51.  
    }

---

全球变暖

 

 

1.  
   #include<iostream>
2.  
   #include<cstdio>
3.  
   #include<cstring>
4.  
   #include<algorithm>
5.  
   #define x first
6.  
   #define y second
7.  
   using namespace std;
8.  
   typedef pair<int, int> PII;
9.  
   const int N = 1010;
10.  
    int n;
11.  
    char g[N][N];
12.  
    bool st[N][N];
13.  
    PII q[N * N];
14.  
    int dx[4] = { -1,0,1,0 };
15.  
    int dy[4] = { 0,1,0,-1 };
16.  
    // total : 岛屿的板块的数量 bound：邻接海洋的岛屿板块的数量
17.  
    void bfs(int sx, int sy, int& total, int& bound)
18.  
    {
19.  
    int hh = 0;
20.  
    int tt = 0;
21.  
    q[0] = { sx,sy };
22.  
    st[sx][sy] = true;
23.  
     
24.  
    while (hh <= tt)
25.  
    {
26.  
    PII t = q[hh ];
27.  
     
28.  
    total ;
29.  
    bool is_bound = false;
30.  
    for (int i = 0; i < 4; i )
31.  
    {
32.  
    int x = t.x dx[i];
33.  
    int y = t.y dy[i];
34.  
    if (x < 0 || x >= n || y < 0 || y >= n) continue;
35.  
    if (st[x][y]) continue;//如果已经走过了
36.  
    if (g[x][y] == '.')//上下左右之中有一个为海
37.  
    {
38.  
    is_bound = true;
39.  
    continue;
40.  
    }
41.  
    q[ tt] = { x,y };
42.  
    st[x][y] = true;
43.  
    }
44.  
    if (is_bound) bound ;//只要上下左右之中有一个为海，那么它就是边界
45.  
    }
46.  
    }
47.  
     
48.  
    int main()
49.  
    {
50.  
    cin >> n;
51.  
     
52.  
    for (int i = 0; i < n; i ) cin >> g[i];
53.  
     
54.  
    int cnt = 0;
55.  
    for(int i=0;i<n;i )
56.  
    for(int j=0;j<n;j )
57.  
    if (!st[i][j] && g[i][j] == '#')
58.  
    {
59.  
    int total = 0;
60.  
    int bound = 0;
61.  
    bfs(i, j, total, bound);
62.  
    if (total == bound) cnt ;
63.  
    }
64.  
    cout << cnt << endl;
65.  
     
66.  
    return 0;
67.  
    }

---

这篇好文章是转载于：学新通技术网