hdoj 1429 勝利大逃亡(續) 【BFS+狀態壓縮】
來源：程序員人生 發布時間：2014-09-04 04:31:11 閱讀次數：3207次
題目：hdoj 1429 勝利大逃亡(續)
相同題目：
題意：中文的，自己看
分析：題目是求最少的逃亡時間，確定用BFS
這個題目的難點在于有幾個鎖對于幾把鑰匙，唯一的對應關系，不能用直接的標記法，因為一個圖可能需要搜索多次。
仔細分析的話會發現，圖的搜索次數是和鑰匙的出現次數相關，那么我們可以用二進制的0 和 1 來表示第幾把鑰匙出現過沒有，所以我們可以用狀態壓縮來標記那個鑰匙出現過，然后用三維標記，第三維表示出現幾個鑰匙了的情況下圖的點的搜索情況。其他就和簡單的一樣。
AC代碼：
#include <cstdio>
#include<iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 25;
char map[N][N];
int vis[N][N][1<<11];
struct Node
{
int x,y,step;
int key;
};
int dx[6]={0,0,1,-1};
int dy[6]={1,-1,0,0};
int m,n,t;
int BFS(Node st,Node en)
{
memset(vis,0,sizeof(vis));
st.step = 0;st.key=0;
queue<Node> q;
q.push(st);
Node tmp1,tmp2;
while(!q.empty())
{
tmp1 = q.front();
q.pop();
if(tmp1.x==en.x && tmp1.y==en.y)
return tmp1.step;
for(int i=0;i<4;i++)
{
tmp2.x=tmp1.x+dx[i];
tmp2.y=tmp1.y+dy[i];
tmp2.step = tmp1.step+1;
tmp2.key = tmp1.key;
if(map[tmp2.x][tmp2.y]>='a' && map[tmp2.x][tmp2.y]<='j')
tmp2.key = tmp2.key|(1<<(map[tmp2.x][tmp2.y]-'a'));
if(map[tmp2.x][tmp2.y]=='*' || tmp2.step>=t)
continue;
if(vis[tmp2.x][tmp2.y][tmp2.key]==0 && tmp2.x>=1 && tmp2.y>=1 && tmp2.x<=m && tmp2.y<=n)
{
vis[tmp2.x][tmp2.y][tmp2.key]=1;
if(map[tmp2.x][tmp2.y]>='A' && map[tmp2.x][tmp2.y]<='J')
{
if(tmp2.key&(1<<map[tmp2.x][tmp2.y]-'A'))
q.push(tmp2);
}
else
q.push(tmp2);
}
}
}
return -1;
}
int main()
{
//freopen("Input.txt","r",stdin);
while(~scanf("%d%d%d",&m,&n,&t))
{
Node st,en;
for(int i=1;i<=m;i++)
{
getchar();
for(int j=1;j<=n;j++){
scanf("%c",&map[i][j]);
if(map[i][j]=='@')
st.x=i,st.y=j;
if(map[i][j]=='^')
en.x=i,en.y=j;
}
}
int ans=BFS(st,en);
if(ans<t)
printf("%d
",ans);
else
puts("-1");
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
