时间限制：1s 空间限制：256m
题目描述：
有一个 𝑛×𝑚的地图，空地为’.‘，高楼为’#'，小信的家在 ‘S’。
小信想找一条锻炼身体的路径，路径需要从家出发，不经过相同的空地，最后回到家。出于锻炼身体的目的，这条路径的长度必须至少为4，也就是说除了终点和起点都是家以外，经过的不同的空地个数至少为 3。
小信想知道这样的路径存不存在。当然，小信无法通过有高楼的地方，所以可能不存在这样的路径。
输入格式：
第一行包含两个整数 𝑛,𝑚.
接下来包含一个 𝑛×𝑚的地图，地图只包含 ‘.’,‘#’,‘S’ 三种字符。
输出格式：
第一行包含两个整数 𝑛,𝑚.
接下来包含一个 𝑛×𝑚的地图，地图只包含 ‘.’,‘#’,‘S’ 三种字符。
约定：
对于100%的数据，2<=n,m<=10^6，4<=n*m<=10^6。
样例1输入
4 4
....
#.#.
#S#.
....
样例1输出
Yes
样例2输入
4 4
.#..
#.#.
#S#.
....
样例2输出
No
根据题意可以看出，这是一道搜索题。
它的起点与终点相同，且路径的长度必须>=4。
那我们该用DFS还是BFS呢？
首先我们考虑一下BFS，
我的想法是：
题目中说到不能走相同的路径，说明我们需要用一个数组来记录走过的路(以下简称为vis)
但BFS可能导致原有路径被vis记录(也就是不能走了)
具体请看下图(仅代表个人想法，绿色为vis标记部分，红色为BFS搜索路径，黄色为正解):
画的有点丑，不喜勿喷
所以我选择用DFS来写这道题
但，还有个问题
n和m的值都<=10^6，地图怎么存呢？
实际上，地图并不需要存储(不过如果你想存，可以用vector开个二维数组)
可以用vis将高楼(走不了的地方)设为1，就像走过的路一样不能走
当然，vis也因为数据问题不能用数组存储，可以用Map或二维vector(我用的是Map)
以下为AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
map<pair<int,int>,int> vis;
int ax,ay;
int ux[4]={1,-1,0,0},uy[4]={0,0,1,-1};
void dfs(int x,int y,int step){
for(int i=0;i<4;i++){
int px=x+ux[i],py=y+uy[i];
if(px<1||px>n||py<1||py>m||vis[{px,py}]) continue;
if(px==ax&&py==ay){
if(step+1>=4){
cout<<"Yes";
exit(0);
}
continue;
}
vis[{px,py}]=1;
dfs(px,py,step+1);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='S') ax=i,ay=j;
if(c=='#') vis[{i,j}]=1;
else vis[{i,j}]=0;
}
}
dfs(ax,ay,0);
cout<<"No";
return 0;
}
