nowcoder 2020/6/20 G-遗迹逃亡

为了寻找稀有的宝可梦，小梁进了一个古代遗迹中。在一次意外的触发之下，她复活了超古代宝可梦化石翼龙并激怒了对方，现在化石翼龙准备攻击小梁，她要逃离这个遗迹了。
但化石翼龙的实力过于强大，让这个本就历经风霜的遗迹开始了毁灭性的崩塌，有大量的落石下落，现在我们要帮助小梁逃离这个遗迹。
遗迹是一个N * M 的矩阵，g表示该遗迹的出口；s表示小梁所处位置；现在遗迹中有大量落石正在下落。因为小梁不能翻越这些落石，所以必须绕开，同时小梁只能走上下左右4个方向。
现在小梁要开始逃亡了，那么小梁可以顺利逃出遗迹吗？

示例1
输入

10 10
s.........
#########.
#.......#.
#..####.#.
##.##.#.#.
##.##.#.#.
g...#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

输出

Yes

非常简单的深搜，但是太久没写了，没有设置flag数组判断该点有没有走过，导致dfs一直死循环出不来了，这也能卡半个多小时是真想不到啊^^

#include<bits/stdc++.h>
using namespace std;

char f[505][505];
int flag[505][505];//一定要记得设置一个flag一定要记得设置一个flag一定要记得设置一个flag一定要记得设置一个flag一定要记得设置一个flag
int n,m,ans=0;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};

void dfs(int x,int y)
{	
	if(x<1||x>n||y<1||y>m||f[x][y]==‘#‘||flag[x][y]==1)return;
	flag[x][y]=1;
	if(f[x][y]==‘g‘)ans=1;
	for(int k=0;k<4;k++)dfs(x+dx[k],y+dy[k]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>f[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(f[i][j]==‘s‘)dfs(i,j);
		}
	}	
	if(ans)cout<<"Yes";
	else cout<<"No";
	return 0;
}

nowcoder 2020/6/20 G-遗迹逃亡

原文：https://www.cnblogs.com/LiangYC1021/p/13169937.html