首页 > 代码库 > ouc shanghairegion#1E
ouc shanghairegion#1E
E - Maze
Time Limit:1000MS Memory Limit:100000KB 64bit IO Format:%I64d & %I64uDescription
This story happened on the background of Star Trek.
Spock, the deputy captain of Starship Enterprise, fell into Klingon’s trick and was held as prisoner on their mother planet Qo’noS.
The captain of Enterprise, James T. Kirk, had to fly to Qo’noS to rescue his deputy. Fortunately, he stole a map of the maze where Spock was put in exactly.
The maze is a rectangle, which has n rows vertically and m columns horizontally, in another words, that it is divided into n*m locations. An ordered pair (Row No., Column No.) represents a location in the maze. Kirk moves from current location to next costs 1 second. And he is able to move to next location if and only if:
Next location is adjacent to current Kirk’s location on up or down or left or right(4 directions)
Open door is passable, but locked door is not.
Kirk cannot pass a wall
There are p types of doors which are locked by default. A key is only capable of opening the same type of doors. Kirk has to get the key before opening corresponding doors, which wastes little time.
Initial location of Kirk was (1, 1) while Spock was on location of (n, m). Your task is to help Kirk find Spock as soon as possible.
Spock, the deputy captain of Starship Enterprise, fell into Klingon’s trick and was held as prisoner on their mother planet Qo’noS.
The captain of Enterprise, James T. Kirk, had to fly to Qo’noS to rescue his deputy. Fortunately, he stole a map of the maze where Spock was put in exactly.
The maze is a rectangle, which has n rows vertically and m columns horizontally, in another words, that it is divided into n*m locations. An ordered pair (Row No., Column No.) represents a location in the maze. Kirk moves from current location to next costs 1 second. And he is able to move to next location if and only if:
Next location is adjacent to current Kirk’s location on up or down or left or right(4 directions)
Open door is passable, but locked door is not.
Kirk cannot pass a wall
There are p types of doors which are locked by default. A key is only capable of opening the same type of doors. Kirk has to get the key before opening corresponding doors, which wastes little time.
Initial location of Kirk was (1, 1) while Spock was on location of (n, m). Your task is to help Kirk find Spock as soon as possible.
Input
The 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 x i1, y i1, x i2, y i2, g i; when g i >=1, represents there is a gate of type gi between location (x i1, y i1) and (x i2, y i2); when g i = 0, represents there is a wall between location (x i1, y i1) and (x i2, y i2), ( | x i1 - x i2 | + | y i1- y i2 |=1, 0<= g i <=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 x i1, y i1 and q i respectively. That means the key type of q i locates on location (x i1, y i1), (1<= q i<=p).
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 x i1, y i1, x i2, y i2, g i; when g i >=1, represents there is a gate of type gi between location (x i1, y i1) and (x i2, y i2); when g i = 0, represents there is a wall between location (x i1, y i1) and (x i2, y i2), ( | x i1 - x i2 | + | y i1- y i2 |=1, 0<= g i <=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 x i1, y i1 and q i respectively. That means the key type of q i locates on location (x i1, y i1), (1<= q i<=p).
Output
Output the possible minimal second that Kirk could reach Spock.
If there is no possible plan, output -1.
If there is no possible plan, output -1.
Sample Input
4 4 991 2 1 3 21 2 2 2 02 1 2 2 02 1 3 1 02 3 3 3 02 4 3 4 13 2 3 3 03 3 4 3 04 3 4 4 022 1 24 2 1
Sample Output
14
orz陶神，代码简短有力，学习了。学长是用状态压缩来存钥匙的，值得学习，上大神代码，无限YM
/**Author: Ouc_Sky*Problom: E(Shanghai2014)*Algorithm: zhuangya dp*Time: 2014/11/20*/#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>#define debug 0using namespace std;const int MAXN = 52;struct node{ int x,y,key,step;};int n,m,p,k,s;int ans;int gate[MAXN][MAXN][MAXN][MAXN];int key[MAXN][MAXN];bool vis[MAXN][MAXN][1<<11];int dx[]={1,-1,0,0};int dy[]={0,0,1,-1}; //right left down upint main(){ while(~scanf("%d%d%d",&n,&m,&p)) { memset(gate,-1,sizeof(gate)); memset(key,0,sizeof(key)); memset(vis,false,sizeof(vis)); ans = -1; scanf("%d",&k); for(int i=0;i<k;i++) { int x1,y1,x2,y2,gi; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&gi); gate[x1][y1][x2][y2] = gi; gate[x2][y2][x1][y1] = gi; } if (debug) printf("input2 Yes\n"); scanf("%d",&s); for(int i=0;i<s;i++) { int x,y,q; scanf("%d%d%d",&x,&y,&q); key[x][y] = (1<<(q-1)) | key[x][y]; } queue<node> que; struct node next = {1,1,0,0}; que.push(next); while(!que.empty()) { struct node now = que.front(); que.pop(); if(now.x == n && now.y == m) { ans = now.step; break; } now.key = key[now.x][now.y] | now.key; for(int i=0;i<4;i++) { next.x = now.x+dx[i]; next.y = now.y+dy[i]; if(now.x >= 1 && now.x <= n && now.y >= 1 && now.y <= m) { int thisGate = gate[now.x][now.y][next.x][next.y]; if( thisGate > 0 && (now.key & (1<<(thisGate-1) )) || (thisGate == -1)) { if (!vis[next.x][next.y][now.key]) { vis[next.x][next.y][now.key] = true; next.key = now.key; next.step = now.step +1; que.push(next); } } } } } printf("%d\n",ans); }//<end of while(!scanf)> return 0;}
ouc shanghairegion#1E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。