HDU-1429
蒟蒻怎么WA了TAT
人能想到的数据我都测了QAQ
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
using namespace std;
char c;
int n,m,T;
int qx,qy;
bool vis[24][24][1027];
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
struct node
{
int x,y,key,t;
};
int zx,zy;
char mp[24][24];
node np,sp,tp;
queue<node> q;
int bfs(int x,int y)
{
sp.x=x;
sp.y=y;
q.push(sp);
vis[x][y][0]=1;
while(!q.empty())
{
np=q.front();
q.pop();
if(np.t>T) return -1;
if(np.x==zx&&np.y==zy)
{
return np.t;
}
for(int i=1;i<=4;++i)
{
tp.x=np.x+dx[i];
tp.y=np.y+dy[i];
tp.t=np.t+1;
tp.key=np.key;
if(tp.x>0&&tp.y>0&&tp.x<=n&&tp.y<=m)
if(mp[tp.x][tp.y]!='*'&&!vis[tp.x][tp.y][tp.key])
{
if(mp[tp.x][tp.y]>='a' && mp[tp.x][tp.y]<='j')
{
int numkey=mp[tp.x][tp.y]-'a';
tp.key|=(1<<numkey);
}
if(mp[tp.x][tp.y]>='A' && mp[tp.x][tp.y]<='J')
{
int numlock=mp[tp.x][tp.y]-'A';
if(!(tp.key&(1<<numlock)))
continue;
}
vis[tp.x][tp.y][tp.key]=1;
q.push(tp);
}
}
}
return -1;
}
int main()
{
while(cin>>n>>m>>T)
{
while(!q.empty()) q.pop();
memset(mp,'*',sizeof(mp));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
cin>>mp[i][j];
if(mp[i][j]=='@')
{
qx=i;
qy=j;
}
if(mp[i][j]=='^')
{
zx=i;
zy=j;
}
}
int besttime=bfs(qx,qy);
if(besttime>=T)
{
cout<<-1<<endl;
return 0;
}
cout<<besttime<<endl;
}
return 0;
}