本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-06 22:57:52

题外话

赛时很快就想出了一个自认为错的算法，还随便整了个 hack 数据，然后去看 F 题，G 题。过了半个小时回来看，分析一下发现是对的。不过还是赶在比赛结束前 20min 切了。

做法

搜索。
没错，就是搜索。
当然，不是指数级的爆搜，是记忆化。 从起点开始搜，一旦找到任意一条从起点出发又回到起点的（长度大于 $0$ 的）路径，就退出；搜到一个已经访问到的点就立即返回。

听上去很不对，因为如果第一条路径没走好，还会挡住后面更长的路径搜不到。

但是，请注意，把图画出来之后，你会发现，只要找到任意一条从起点出发又回到起点的（长度大于 $0$ 的）路径，长度都符合要求，而显然只要存在从起点出发又回到起点的（长度大于 $0$ 的）路径，记忆化搜索肯定能找到其中一条。
举个极端的例子：

记忆化搜索找到了最短的一条从起点出发又回到起点的长度大于 $0$ 的路径，而这路径符合要求。

Code

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e6+5;
string str[maxn];
map<pair<int,int>,bool> vis;
int h,w;
int sth,stl;
int ans=0;
void dfs(int i,int j,int cnt)
{
	if(ans||i>=h||i<0||j>=w||j<0||str[i][j]=='#')return;
	if(!(i==sth&&j==stl)&&vis.find(make_pair(i,j))!=vis.end())return;
	vis[make_pair(i,j)]=1;
	if(i==sth&&j==stl&&cnt!=0)
	{
		if(cnt>=4)ans=1;
		return;
	}
	dfs(i+1,j,cnt+1);
	dfs(i-1,j,cnt+1);
	dfs(i,j-1,cnt+1);
	dfs(i,j+1,cnt+1);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>h>>w;
	for(int i=0;i<h;i++)
	{
		cin>>str[i];
		for(int j=0;j<str[i].size();j++)
		{
			if(str[i][j]=='S')
			{
				sth=i,stl=j;
			}
		}
	}
	dfs(sth,stl,0);
	if(ans)printf("Yes");
	else printf("No");
	return 0;
}