又开始刷题了
题意：略过。
分析：主要是确定状态量，除了坐标(x,y)之外，还有一个key状态，就好比手上拿着一串钥匙。状态可以用位运算来表示：key&(x,y)表示判断有没有这扇门的钥匙，key|(x,y)表示捡起了一把钥匙。
错误：1、开标记数组mark[][][]，key状态大小顺手开成key，其实应该是1<<key
2、判断应该先判wall()，顺序颠倒倒是RE（访问越界）
3、key<=10：只有 a-j 共10种钥匙
思考：这道题其实应该是有漏洞的，因为魔王只是查看男主是否在原位置上，并没有说明检查钥匙，如此一来男主只要在时间限定T之内找到一把钥匙，就向逃亡迈进了一步，换句话说就是状态被大幅度增加——不再是必须在T内找到出口“^”。进一步说，若魔王发现男主不在原位置，不仅把他放回原位，还还原钥匙的位置，那么如果在时间限定T内，他能够找到钥匙并返回原位，又是否算是通过了这次检查呢？以上两种情况但凡一种成立，测试样例2都可以通过。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
using namespace std; const int MAXN=;
const int KEY=; int dir[][]={,-,,,-,,,}; struct Node{
int x,y,t,key;
Node(){}
Node(int _x,int _y,int _t,int _key):x(_x),y(_y),t(_t),key(_key){}
}; char g[MAXN][MAXN];
int mark[MAXN][MAXN][<<KEY];
queue<Node>q; int n,m,T; bool wall(int x,int y)
{
if(x<||x>=n||y<||y>=m)
return true;
if(g[x][y]=='*')
return true;
return false;
} int Num(char ch)
{
return ch-(isupper(ch)?'A':'a');
} int bfs(int sx,int sy)
{
while(!q.empty())
q.pop(); memset(mark,,sizeof(mark));
q.push(Node(sx,sy,,));
while(!q.empty())
{
Node e=q.front();q.pop(); if(e.t>=T)
break; for(int i=;i<;i++)
{
int dx=e.x+dir[i][];
int dy=e.y+dir[i][];
int dt=e.t+;
int dkey=e.key; char ch=g[dx][dy]; if(wall(dx,dy))
continue;
if(dt>=T||mark[dx][dy][dkey])
continue;
if(isupper(ch)&&!(dkey&(<<Num(ch))))
continue;
if(islower(ch))
dkey=dkey|(<<Num(ch)); if(g[dx][dy]=='^')
return dt; mark[dx][dy][dkey]=;
q.push(Node(dx,dy,dt,dkey));
}
}
return -;
} int main()
{
while(~scanf("%d%d%d",&n,&m,&T))
{
for(int i=;i<n;i++)
scanf("%s",g[i]); int sx,sy,ex,ey;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(g[i][j]=='@'){
sx=i;
sy=j;
g[i][j]='.';
} printf("%d\n",bfs(sx,sy));
}
return ;
}