【TJOI2009】宝藏
看到走地图问题，自然联想到广搜，这个题前两篇题解讲的很清楚了，要带着机关状态走。最多只有十个机关，考虑状压。但是大佬们的装压我都看不懂捏，特意来补一下基础二进制知识。
我们将每个机关状态压成一个二进制数的每一位，第 $i$ 个机关在这个数中就是第 $i$ 位，那么检查和修改就只要用到下面两个操作。
(n>>k)&1 //取出n在二进制下的第k位
n^(1<<k) //将n在二进制下的第k位取反
由于奇妙的题意，所以这个题有很多小坑，一个格子可能既操控机关，又被机关影响。一个操控机关的格子可以反复横跳去踩。等等。
剩下的详见代码吧，写了注释的捏。
#include<bits/stdc++.h>
#define ll long long
#define MAX 50
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
int r,c,n,ans;
char m[MAX][MAX];
int br,bc,er,ec;
bool cause[MAX][MAX],so[MAX][MAX]; //cause是操控机关的 so是被机关影响的
struct op
{
int r1,c1,r2,c2;
}o[20];
bool vis[MAX][MAX][3000]; //二进制下十个机关最多 1<<10=2048 三维分别是坐标和机关状态，这样可以防止无意义的横跳
struct node
{
int x,y;
int mac,dis; //dis是步数 mac是机关状态
};
queue<node> q;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void check(int x,int y,node &a) //把每个这个格子操控的机关都打开或者关上
{
for(int i=1;i<=n;i++)
if(x==o[i].r1&&y==o[i].c1)
a.mac=a.mac^(1<<i);
return;
}
int cheeck(int x,int y,int state) //可能多个机关操控一个格子，所以要把每个与其相关的操控机关都检查一遍
{
int k=0;
for(int i=1;i<=n;i++)
if(x==o[i].r2&&y==o[i].c2&&((state>>i)&1))
k^=1;
return k;
}
int main()
{
r=read(),c=read();
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>m[i][j];
if(m[i][j]=='S') br=i,bc=j,m[i][j]='.';
if(m[i][j]=='T') er=i,ec=j,m[i][j]='.';
}
n=read();
for(int i=1;i<=n;i++)
{
o[i].r1=read(),o[i].c1=read(),o[i].r2=read(),o[i].c2=read();
cause[o[i].r1][o[i].c1]=1,so[o[i].r2][o[i].c2]=1;
}
node t;
t.x=br,t.y=bc,t.dis=0,t.mac=0;
vis[t.x][t.y][t.mac]=1;
q.push(t);
while(!q.empty())
{
t=q.front(); q.pop();
if(t.x==er&&t.y==ec)
{
ans=t.dis;
break;
}
for(int i=0;i<4;i++)
{
int tx=dx[i]+t.x,ty=dy[i]+t.y;
if(tx>=1&&ty>=1&&tx<=r&&ty<=c)
{
if(!cause[tx][ty]&&!so[tx][ty]&&m[tx][ty]=='.')
{//都不是
node tt;
tt.x=tx,tt.y=ty,tt.dis=t.dis+1,tt.mac=t.mac;
if(!vis[tt.x][tt.y][tt.mac])
{
vis[tt.x][tt.y][tt.mac]=1;
q.push(tt);
}
}
if(cause[tx][ty] && !so[tx][ty])
{//cause
if(m[tx][ty]!='.') continue;
node tt;
tt.x=tx,tt.y=ty,tt.dis=t.dis+1,tt.mac=t.mac;
check(tx,ty,tt);
if(!vis[tt.x][tt.y][tt.mac])
{
vis[tt.x][tt.y][tt.mac]=1;
q.push(tt);
}
}
if(so[tx][ty])
{//so+cause || so 这个地方要注意，可能是so套着cause，因为这个第一发拿了60
int state=cheeck(tx,ty,t.mac);
if((state&&m[tx][ty]=='#')||(!state&&m[tx][ty]=='.'))
{//能走
if(cause[tx][ty])
{
//cause+so
node tt;
tt.x=tx,tt.y=ty,tt.dis=t.dis+1,tt.mac=t.mac;
check(tx,ty,tt);
if(!vis[tt.x][tt.y][tt.mac])
{
vis[tt.x][tt.y][tt.mac]=1;
q.push(tt);
}
continue;
}
//只so
node tt;
tt.x=tx,tt.y=ty,tt.dis=t.dis+1,tt.mac=t.mac;
if(!vis[tt.x][tt.y][tt.mac])
{
vis[tt.x][tt.y][tt.mac]=1;
q.push(tt);
}
}
}
}
}
}
cout<<ans;
return (0-0);
}