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