DFS
关于 dfs, 我的理解就是深度搜索, 找到所有与入口相连的路径, 可以用于迷宫求出口, 利用递归的思想, 进行搜索返回所有值.
比如, 给你两个值分别表示迷宫的长和宽, 迷宫有一个入口, 一个出口, 判断能否从迷宫出来, 入口用 "s" 表示, 出口用 "e" 表示, 墙壁用 "#" 表示, 路用 "." 表示
输入: 3 4
- s...
- .##.
- #..e
- 4 4
- s...
- ..##
- #.##
- ###e
输出: You can gou out!
- Trapped!
- #include "pch.h"
- #include <cstdio>
- #include <cstring>
- #include <queue>
- #include<cstdio>
- #include <algorithm>
- #include <iostream>
- #include <istream>
- using namespace std;
- int n, m, si, sj, ei, ej;
- char ditu[30][30];
- int flag[30][30];
- int s = 0;
- void sou(int x, int y)
- {
- if (x <0 || x>= n || y <0 || y>= m || flag[x][y] == 1)
- return;
- if (x == ei && y == ej)
- s = 1;
- // 把使用的地方标记为 1, 防止下次再用
- flag[x][y] = 1;
- // 四个方向
- sou(x + 1, y);
- sou(x - 1, y);
- sou(x, y + 1);
- sou(x, y - 1);
- }
- int main()
- {
- int i, j;
- while (cin>> n>> m)
- {
- getchar();
- s = 0;
- memset(flag, 0, sizeof(flag));// 还原 flag,flag 用来标记墙壁并且标记使用过的地方
- for (i = 0; i <n; i++)
- {
- for (j = 0; j < m; j++)
- {
- cin>> ditu[i][j];// 输入地图
- if (ditu[i][j] == 's')
- {
- si = i;
- sj = j;
- }
- if (ditu[i][j] == 'e')
- {
- ei = i;
- ej = j;
- }
- if (ditu[i][j] == '#')
- flag[i][j] = 1;
- }
- getchar();
- }
- sou(si, sj);// 查找
- if (s == 0)
- cout << "Trapped!" << endl;
- else
- cout << "You can go out!" << endl;
- }
- return 0;
- }
关于 dfs
来源: http://www.bubuko.com/infodetail-3034503.html