HDoj 1429勝利大逃亡(続)【bfs好題】
勝利大逃亡(続)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7340 Accepted Submission(s): 2544
Problem Description
Ignatiusは再び魔王に捕らえられた(彼がどうしてこんなに魔王に好かれるのか分からない)......
今回の魔王は前回の教訓を汲み取り、Ignatiusをn*mの地牢に閉じ込め、地牢のある場所に鍵付きのドアを取り付け、鍵は地牢の別の場所に隠された.最初はIgnatiusが(sx,sy)の位置に閉じ込められ、牢屋のドアを離れて(ex,ey)の位置にいた.Ignatiusは毎分1つの座標から隣接する4つの座標のうちの1つしか歩けない.魔王はt分ごとに地牢を視察し、Ignatiusがその場にいないことに気づいたら彼を連れて帰った.いくつかの試みを経て、Ignatiusは地牢全体の地図を描いた.今、彼が再び逃亡に成功するかどうかを計算してください.魔王が今度視察する前に出口に出て刑務所を離れても、魔王が帰ってきたときに出口に着いたり、出口に着いていない場合は逃亡に失敗します.
Input
各試験データの最初の行には、3つの整数n,m,t(2<=n,m<=20,t>0)がある.次のn行mは、以下を含む地獄の地図として列挙される.
・代表路
*は壁を表します
@はIgnatiusの開始位置を表します
^地牢の出口を代表する
A-Jは鍵付きドアを表し、対応する鍵はそれぞれa-jである
a-jは鍵を表し、対応するドアはそれぞれA-Jである
各テストデータのセットの間に空の行があります.
Output
各テストデータのセットについて、逃亡に成功した場合は、出力に何分かかりますか.できない場合は-1を出力します.
Sample Input
Statistic | Submit | Discuss | Note
代码：
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7340 Accepted Submission(s): 2544
Problem Description
Ignatiusは再び魔王に捕らえられた(彼がどうしてこんなに魔王に好かれるのか分からない)......
今回の魔王は前回の教訓を汲み取り、Ignatiusをn*mの地牢に閉じ込め、地牢のある場所に鍵付きのドアを取り付け、鍵は地牢の別の場所に隠された.最初はIgnatiusが(sx,sy)の位置に閉じ込められ、牢屋のドアを離れて(ex,ey)の位置にいた.Ignatiusは毎分1つの座標から隣接する4つの座標のうちの1つしか歩けない.魔王はt分ごとに地牢を視察し、Ignatiusがその場にいないことに気づいたら彼を連れて帰った.いくつかの試みを経て、Ignatiusは地牢全体の地図を描いた.今、彼が再び逃亡に成功するかどうかを計算してください.魔王が今度視察する前に出口に出て刑務所を離れても、魔王が帰ってきたときに出口に着いたり、出口に着いていない場合は逃亡に失敗します.
Input
各試験データの最初の行には、3つの整数n,m,t(2<=n,m<=20,t>0)がある.次のn行mは、以下を含む地獄の地図として列挙される.
・代表路
*は壁を表します
@はIgnatiusの開始位置を表します
^地牢の出口を代表する
A-Jは鍵付きドアを表し、対応する鍵はそれぞれa-jである
a-jは鍵を表し、対応するドアはそれぞれA-Jである
各テストデータのセットの間に空の行があります.
Output
各テストデータのセットについて、逃亡に成功した場合は、出力に何分かかりますか.できない場合は-1を出力します.
Sample Input
4 5 17 @A.B. a*.*. *..*^ c..b* 4 5 16 @A.B. a*.*. *..*^ c..b*
Sample Output
16 -1
Author
LL
Source
ACM暑期集训队练习赛（三）
Recommend
linle
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int n,m,t;
char mp[25][25];
int vis[25][25][1<<11];//a,b,c,d,e,f,g,h,i,j
int sx,sy,ex,ey;
int ans;
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
struct node
{
int x,y,step,key;
}a,temp;
int judge()
{
if(temp.x<0||temp.x>=n) return 0;
if(temp.y<0||temp.y>=m) return 0;
if(temp.step>t) return 0;
if(mp[temp.x][temp.y]=='*') return 0;
return 1;
}
void bfs()
{
queueq;
a.x=sx;a.y=sy;a.step=0,a.key=0;
q.push(a);
memset(vis,0,sizeof(vis));
vis[sx][sy][0]=1;
while(!q.empty())
{
a=q.front();
q.pop();
for(int i=0;i<4;i++)
{
temp.x=a.x+dx[i];
temp.y=a.y+dy[i];
temp.step=a.step+1;
if(judge())
{
if(mp[temp.x][temp.y]>='a'&&mp[temp.x][temp.y]<='j')
{
temp.key=a.key|((1<='A'&&mp[temp.x][temp.y]<='J')
{
temp.key=a.key;
if(temp.key&(1<