AT1350 深さ優先探索（洛谷 深度优先搜索+记忆化）

高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。

现在给出地图：

s：代表高桥先生的家

g：代表鱼店

.：代表道路

#：代表墙壁

高桥先生不能穿过墙壁。

输入：第一行输入n(1<=n<=500),m(1<=m<=500)代表小区的长和宽，接下来n行每行m个字符，描述小区中的每个格子。

输出：如果高桥先生能到达鱼店，输出"Yes"，否则输出"No"。

输入输出样例 输入 #1

复制

4 5

s####

…#

#…g 输出 #1

复制

No输入 #2

复制

4 4

…s

…

…

.g… 输出 #2

复制

Yes输入 #3

复制

10 10

s…

#########.

#…#.

#…####.#.

##…#.#.

#####.#.#.

g.#.#.#.#.

#.#.#.#.#.

###.#.#.#.

#…#… 输出 #3

复制

No输入 #4

复制

10 10

s…

#########.

#…#.

#…####.#.

##…#.#.

#####.#.#.

g.#.#.#.#.

#.#.#.#.#.

#.#.#.#.#.

#…#… 输出 #4

复制

Yes输入 #5

复制

1 10

s…####…g 输出 #5

复制

No

思路：其实这道题目是简单到不能简单的一道深搜题目。但是我一开始的想法是需要回溯的，但是回溯做的话，是会超时的。如果当前状态走过了，但是无法走到终点，按照之前的做法就取消标记，然后下次从别的点走到这个点的时候，结果仍然是走不到。那么我们就不取消标记了，如果某一个状态可以直接走到终点，就直接返回，如果走不到终点，仍然不取消标记，别的点走到这一个点的时候，就会知道这个点无法走到终点。这一操作类似于记忆化的操作。

代码如下：

#include <iostream>#include <string>using namespace std;int n,m;int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}}; //定义方向数组 ； string maze[1100]; //定义地图；bool vis[1100][1100]; //定义标记数组， 记录当前点是否走过； bool in(int x,int y) {return x >= 0 && x < n && y >= 0 && y < m;} // 判断函数，判断当前点是否位于地图内； bool dfs(int x,int y) {if (maze[x][y] == 'g') {return true;} //判断是否到达；； vis[x][y] = 1; //标记当前点； for (int i = 0; i < 4; i++) {// 向四个方向搜索； int tx = x + dir[i][0];int ty = y + dir[i][1];if (in(tx,ty) && maze[tx][ty] != '#' && !vis[tx][ty]) {//在地图内、不是障碍物、未访问则可继续搜索； if (dfs(tx,ty)) {return true; // 在(tx,ty)能到达，在(x,y)也能到达； }}}//若删除标记，则从其他点也可搜索至(x,y)； //从(x,y)无法到达终点，则从其他点到达(x,y)之后也无法到达终点； //故无需回溯； return false;}int main () {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> maze[i];} // 输入地图； int x,y;for (int i = 0; i < n; i++) {// 寻找起点； for (int j = 0; j < m; j++) {if (maze[i][j] == 's') {x = i, y = j;}}}if (dfs(x,y)) {cout << "Yes";} else {cout << "No";}return 0;}

ps：本题用bfs做更好。努力加油a啊