Maze

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 100000/100000K (Java/Other)

Total Submission(s) : 9 Accepted Submission(s) : 3

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

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.

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 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, yi1 and qi respectively. That means the key type of qi locates on location (xi1, yi1), (1<= qi<=p).

Output

Output the possible minimal second that Kirk could reach Spock.

If there is no possible plan, output -1.

Sample Input

Sample Output

Source

2014上海全国邀请赛——题目重现（感谢上海大学提供题目）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
#define maxn 60
int poww[11]={1,2,4,8,16,32,64,128,256,512,1024};
int mp[maxn][maxn];
int vis[maxn][maxn][maxn];
int mark[maxn][maxn][maxn][maxn];
int n,m,p;
int k,s;
/*
钥匙在地图上最好以状态附加的形式出现，
也就是说不必刻意去判断钥匙的存在，
而是每走一步就或运算加上即可。起点也可能有钥匙出现，细节。。。每个位置可能有多个钥匙出现，，，
只要初始化地图时也使用或运算即可，，来描述状态*/int x1,y11,x2,y2,tp;int dir1[]={0,0,-1,1};
int dir2[]={1,-1,0,0};bool judge(int x,int y)
{if(x<=0||x>n) return false;if(y<=0||y>m) return false;return true;
}struct Node
{int x,y;int cnt;//步数int state;//掌握的钥匙Node(int xx=0,int yy=0,int tt=0,int s=0){x=xx;y=yy;cnt=tt;state=s;}
};int BFS()
{queue<Node> seq;seq.push(Node(1,1,0,mp[1][1]));memset(vis,0,sizeof(vis));vis[1][1][mp[1][1]]=1;while(!seq.empty()){Node t=seq.front();seq.pop();//cout<<t.x<<" "<<t.y<<" "<<t.state<<endl;if(t.x==n&&t.y==m) return t.cnt;for(int i=0;i<4;i++){int tx=t.x+dir1[i];int ty=t.y+dir2[i];if(!judge(tx,ty)) continue;//越界int tmp=mark[tx][ty][t.x][t.y];int tstate=(t.state|mp[tx][ty]);//cout<<tmp<<" "<<t.state<<endl;if(tmp==-1||(tmp>0&&(poww[tmp]&t.state)))//如果没墙或者有门但用钥匙可以打开{if(vis[tx][ty][tstate]) continue;vis[tx][ty][tstate]=1;seq.push(Node(tx,ty,t.cnt+1,tstate));}}}return -1;
}int main()
{ios::sync_with_stdio(false);while(cin>>n>>m>>p){memset(mark,-1,sizeof(mark));memset(mp,0,sizeof(mp));cin>>k;for(int i=0;i<k;i++){cin>>x1>>y11>>x2>>y2>>tp;mark[x1][y11][x2][y2]=tp;mark[x2][y2][x1][y11]=tp;}cin>>s;for(int i=0;i<s;i++){cin>>x1>>y11>>tp;mp[x1][y11]|=poww[tp];}cout<<BFS()<<endl;}return 0;
}