P8169 [eJOI 2021] Dungeons

洛谷
非常有意思的一道题目。
由于我们最开始并不知道我们在哪里，所以我们先走所有的起点都可以走的位置。
直接使用 bfs 即可。
然后我们为了走更多步，我们会先尝试判断自己当前位置。
如果对于两个起点，某一相对位置看到的东西不同，那么我们就可以很轻松的分辨出来。
那么我们就能找到一个位置，分两种看到东西的情况，取这两种情况中最小的。
当然这里并不是指这里只能看到两种，而是在原先可能的起点里面，有一部分不同，比如这个点位置有的情况看到的是墙，那么我们就把墙跟金币和空格的情况分开来。
这样做的目的是为了区分开部分起点，起码不能让起点情况递归下去还是和原来一样。
分辨出来在哪些可能位置后，继续拓展，再找可能在哪些位置，如此循环。
如果我们无法分辨了，继续往外走，由于我们考虑的是最坏的情况，所以出去肯定会直接坠机。
但是这样还是太复杂了，我们发现 \(S\le 60\)，刚好可以状态压缩，我们直接通过状压来记录目前递归的所有情况。
对于时间复杂度，我们在每次递归中 bfs 进行拓展和找不同都是 \(O(nm)\)，由于我们每次都会进行分裂，考虑最坏的情况，也就是最后会划分为 \(S\) 个状态，每次进行合并，那么最后会递归到的状态数仍然是 \(S\) 级别的。
那么最终时间复杂度就是 \(O(nmS)\) 了。
代码：
[code]#include#define int long longusing namespace std;int n,m,cnt,x[65],y[65],sta[820][820],stb[820][820][3],dx[]={0,0,1,-1},dy[]={1,-1,0,0},dx2[]={1,1,1,-1,-1,-1,0,0},dy2[]={1,0,-1,1,0,-1,1,-1};char mp[405][405],c[65][820][820];bool vis[820][820];int solve(int st){        queue q;        q.push({405,405});        memset(vis,0,sizeof(vis));        vis[405][405]=1;        while(!q.empty()){                int x=q.front().first,y=q.front().second;                q.pop();                for(int i=0;i

yyds。多谢分享