救基友3（三维BFS）

救基友记3

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描写叙述

话说CZ因为不守基道。被妖怪抓走了。好基友WP在努力讨好高富帅RQ救出CZ的同一时候。CZ也意识到了自己的错误，然后努力的想逃出妖怪的闺房。

妖怪的闺房是一个n*m的矩阵，而且某些地方安装了带锁的门。钥匙藏在闺房另外的某些地方。

刚開始WP被关在(sx,sy)的位置，离开闺房的门在(ex,ey)的位置。WP每分钟仅仅能从一个坐标走到相邻四个坐标中的当中一个。妖怪每t分钟回闺房视察一次。若发现CZ不在原位置便把他再拎回去。经过若干次的尝试，CZ已画出整个闺房的地图。如今请你帮他计算是否能再次成功逃亡。

仅仅要在妖怪下次视察之前走到出口就算离开闺房。假设妖怪回来的时候刚好走到出口或还未到出口都算逃亡失败。

输入

每组測试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为闺房的地图，当中包含:

. 代表路

* 代表墙

@ 代表CZ的起始位置

^ 代表闺房的出口

A-J 代表带锁的门,相应的钥匙分别为a-j

a-j 代表钥匙，相应的门分别为A-J

每组測试数据之间有一个空行。

输出

针对每组測试数据，假设能够成功逃亡。请输出最少须要多少分钟才干离开。假设不能则输出-1。

演示样例输入

4 5 17

@A.B.

a*.*.

*..*^

c..b*

4 5 16

@A.B.

a*.*.

*..*^

c..b*

演示样例输出

16

-1

提示

用进制转换的方法标记第三维，也就是钥匙的状态，開始做的时候思路有错误，就想用二维数组做，可是后来问了P神后。也想明确了，当前状态的钥匙存储状态。无法保证同一时刻正在进行的还有一状态，有无钥匙，所以说必须是三维数组，同一时候存储当前第三维全部该钥匙位置的状态

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <queue>

#define MAX INT_MAX

#define MIN INT_MIN

#define max(a,b) (a>b)?a:b

#define min(a,b) (a<b)?a:b

#define lson l,m,rt>>1

#define rson m+1,r,rt>>1|1

const int SIZE = (1<<10)+10;

using namespace std;

int n,m,T,xx,xy;

struct node{

    int x,y,z,ans;

};

int vis[22][22][SIZE];

char a[22][22];

int mv[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

int Jin_zhi(int tep,int san)

{

    int mm;

      for(int jj = 0;jj<tep;jj++)

        {

            mm = san % 2;

            san /= 2;

        }

        return mm;

}

void BFS()

{

    node f,t;

    queue<node>q ;

    memset(vis,0,sizeof(vis));

    f.x = xx; f.y = xy; f.z = 0;f.ans = 0;

    q.push(f);

    vis[xx][xy][0] = 1 ;

    while(!q.empty())

    {

        t = q.front();

        q.pop();

        if(a[t.x][t.y]=='^' && t.ans < T)

        {

            printf("%d\n",t.ans);

            return ;

        }

        for(int i = 0;i<4;i++)

        {

            f.x = t.x + mv[i][0];

            f.y = t.y + mv[i][1];

            f.z = t.z;

            if(0<=f.x && f.x<n&& 0<=f.y && f.y<m&&!vis[f.x][f.y][f.z])

            {

                if(a[f.x][f.y]=='.' || a[f.x][f.y]=='@' || a[f.x][f.y]=='^')

                {

                    f.ans = t.ans + 1;

                    vis[f.x][f.y][f.z] = 1 ;

                    q.push(f);

                }

                else if('a'<=a[f.x][f.y] && a[f.x][f.y] <='j')

                {

                    f.ans = t.ans + 1;

                    int tep = a[f.x][f.y] - 'a'+1;

                    int san = f.z,flag;

                    flag = Jin_zhi(tep,san);

                    if(!flag)

                        f.z += pow(2,tep-1);

                        vis[f.x][f.y][f.z] = 1;

                        q.push(f);

                }

                else if('A'<=a[f.x][f.y] && a[f.x][f.y] <='J')

                {

                    int tep = a[f.x][f.y] - 'A'+1;

                    f.ans = t.ans + 1;

                    int san = f.z,flag;

                    flag = Jin_zhi(tep,san);

                    if(flag==1)

                    {

                        f.ans = t.ans + 1;

                        vis[f.x][f.y][f.z] = 1;

                        q.push(f);

                    }

                }

            }

        }

    }

    puts("-1");

}

int main()

{

    int flag;

    while(~scanf("%d%d%d",&n,&m,&T))

    {

        flag = 0;

        for(int i = 0;i<n;i++)

        {

            scanf("%*c%s",a[i]);

            if(flag) continue;

            for(int j = 0;j<m;j++)

            {

                if(a[i][j]=='@')

                {

                    xx = i; xy = j;

                    flag = 1;

                    break;

                }

            }

        }

        BFS();

    }

    return 0;

}

cz