ABC276E 题解

__vector__ · 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;
}