HDU - 5094 Maze(状压+bfs)
InputThe input contains many test cases.
Each test case consists of several lines. Three integers are in the first line, which represent n, m and p respectively (1<= n, m <=50, 0<= p <=10).
Only one integer k is listed in the second line, means the sum number of gates and walls, (0<= k <=500).
There are 5 integers in the following k lines, represents xi1, yi1, xi2, yi2, gi; when gi>=1, represents there is a gate of type gi between location (xi1, yi1) and (xi2, yi2); when gi= 0, represents there is a wall between location (xi1, yi1) and (xi2, yi2), ( | xi1- xi2| + | yi1- yi2|=1, 0<= gi<=p )
Following line is an integer S, represent the total number of keys in maze. (0<= S <=50).
There are three integers in the following S lines, represents xi1, yi1and qirespectively. That means the key type of qilocates on location (xi1, yi1), (1<= qi<=p).OutputOutput the possible minimal second that Kirk could reach Spock.
If there is no possible plan, output -1.
Sample Input
4 4 9 9 1 2 1 3 2 1 2 2 2 0 2 1 2 2 0 2 1 3 1 0 2 3 3 3 0 2 4 3 4 1 3 2 3 3 0 3 3 4 3 0 4 3 4 4 0 2 2 1 2 4 2 1
Sample Output
14
题目大意:给定一个棋盘,从(1,1)走到(n,m)有的任意两个格子之间的边视为:通路,门,墙。通路可以直接走,门必须早到相应的钥匙,墙永远不能通过。钥匙在一些给定点的格子中(同一个格子中可能有多把钥匙),问采取怎样的走法可以得到最少的移动步数
解题思路:b[x][y][sta]表示状态为s时到达(x,y)点是否已经到达过,key[x][y]表示钥匙的得到情况的状态。然后进行bfs即可
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<queue> #include<algorithm> #define MAX 55 #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int a[MAX][MAX][MAX][MAX]; int b[MAX][MAX][(1<<10)+5]; int key[MAX][MAX]; int t[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; struct Node{ int x,y,sta,s; }node; queue<Node> q; int main() { int n,m,k,x,i,j; int x1,y1,x2,y2; while(~scanf("%d%d%d",&n,&m,&k)){ scanf("%d",&k); memset(a,-1,sizeof(a)); memset(b,0,sizeof(b)); memset(key,0,sizeof(key)); for(i=1;i<=k;i++){ scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&x); a[x1][y1][x2][y2]=x; a[x2][y2][x1][y1]=x; } scanf("%d",&k); for(i=1;i<=k;i++){ scanf("%d%d%d",&x1,&y1,&x); key[x1][y1]|=1<<(x-1); } if(n==1&&m==1){ printf("0\n"); continue; } while(q.size()){ q.pop(); } node.x=1; node.y=1; node.sta=0; node.s=0; q.push(node); b[1][1][0]=1; int f=0; while(q.size()){ for(i=0;i<4;i++){ int tx=q.front().x+t[i][0]; int ty=q.front().y+t[i][1]; if(tx<1||ty<1||tx>n||ty>m) continue; int fx=q.front().x; int fy=q.front().y; int fsta=q.front().sta; if(a[fx][fy][tx][ty]==0) continue; else if(a[fx][fy][tx][ty]>0){ if(!(fsta&(1<<(a[fx][fy][tx][ty]-1)))) continue; } if(b[tx][ty][fsta]==1) continue; int fs=q.front().s; if(tx==n&&ty==m){ f=fs+1; break; } node.x=tx; node.y=ty; node.sta=fsta|key[tx][ty]; node.s=fs+1; q.push(node); b[tx][ty][node.sta]=1; } if(f>0) break; q.pop(); } if(f==0) printf("-1\n"); else printf("%d\n",f); } return 0; }优质内容筛选与推荐>>