HDOJ 5094 Maze 【状态压缩+BFS】

Maze

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:100000/100000 K (Java/Others)

Total Submission(s): 1356    Accepted Submission(s): 481

Problem Description

This story happened on the background of Star Trek.

Spock, the deputy captain of Starship Enterprise, fell into Klingon’s trick andwas held as prisoner on their mother planet Qo’noS.

The captain of Enterprise, James T. Kirk, had to fly to Qo’noS to rescue hisdeputy. 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 columnshorizontally, in another words, that it is divided into n*m locations. Anordered pair (Row No., Column No.) represents a location in the maze. Kirkmoves from current location to next costs 1 second. And he is able to move tonext location if and only if:

Next location is adjacent to current Kirk’s location on up or down or left orright(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 capableof opening the same type of doors. Kirk has to get the key before openingcorresponding doors, which wastes little time.

Initial location of Kirk was (1, 1) while Spock was on location of (n, m). Yourtask 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 gatesand 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 thereis 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 qi respectively. That means the key type of qilocates 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

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

【题意】给出n*m的迷宫，在迷宫中有p种钥匙和门(但这个p貌似没什么用。。。)，还有一些地方是墙，有墙的地方无法通过，有门的地方拿到钥匙后方可通过。问从迷宫的左上角到迷宫的右下角最小需要走多少步。

【思路】由于这道题迷宫的布置没有像以前那样直接以图的形式给出，所以我们考虑将迷宫扩大为原来的两倍，构造出我们熟悉的模型，然后就可以用BFS解决。

由于涉及到到达门的时候是否已经拿到了相应的钥匙，我们用二进制的形式来表示当前拿到钥匙的情况，在BFS时用vis[x][y][sta]来表示在某个点某种状态是否已经搜到。值得注意的是由于我们把迷宫大小扩大了两倍，扩大后坐标均为偶数的点一定不会走到(自己画个图很好理解),处理好这些就是跑一遍BFS，把搜索结果除2即可。

#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 55;
const int mod = 20090717;
const int INF = 0x3f3f3f;
const double eps = 1e-9;

struct node
{
    int x,y,sta,step;
}now,nex;

int n,m;
int tx,ty;
int need[maxn][maxn];
int have[maxn][maxn];
int vis[maxn][maxn][1<<12];
int wall[maxn][maxn];
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

bool inbound(const node &a)
{
    return a.x>=1&&a.x<=2*n-1&&a.y>=1&&a.y<=2*m-1;
}

void bfs(int x,int y)
{
    mst(vis,0);
    queue<node>q;
    now.x=x;
    now.y=y;
    now.sta=have[x][y];
    now.step=0;
    q.push(now);
    vis[now.x][now.y][now.step]=1;
    while(q.size())
    {
        now=q.front();
        q.pop();
        if(now.x==tx&&now.y==ty)
        {
            int ans=now.step/2;
            printf("%d\n",ans);
            return;
        }
        for(int i=0;i<4;i++)
        {
            nex.x=now.x+dir[i][0];
            nex.y=now.y+dir[i][1];
            if(nex.x%2==0&&nex.y%2==0) continue;
            if(inbound(nex)&&wall[nex.x][nex.y]==0)
            {
                nex.step=now.step+1;
                nex.sta=now.sta|have[nex.x][nex.y];
                if((nex.sta&need[nex.x][nex.y])==need[nex.x][nex.y]&&vis[nex.x][nex.y][nex.sta]==0)
                {
                    vis[nex.x][nex.y][nex.sta]=1;
                    q.push(nex);
                }
            }
        }
    }
    puts("-1");
    return;
}

int main()
{
    int k,p;
    int x,y,xx,yy;
    int kind;
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        mst(vis,0);
        mst(have,0);
        mst(need,0);
        mst(wall,0);
        tx=2*n-1;
        ty=2*m-1;
        scanf("%d",&k);
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&kind);
            x=x*2-1,y=y*2-1;
            xx=xx*2-1,yy=yy*2-1;
            for(int i=x;i<=xx;i++)
            for(int j=y;j<=yy;j++)
            {
                if(i==x&&j==y) continue;
                if(i==xx&&j==yy) continue;
                if(kind==0)
                {
                    wall[i][j]=1;
                }
                need[i][j]|=(1<<kind);
            }
        }
        scanf("%d",&k);
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&x,&y,&kind);
            x=x*2-1;
            y=y*2-1;
            have[x][y]|=(1<<kind);
        }
        bfs(1,1);
    }
    return 0;
}