首页 > 代码库 > sdut2193救基友记3（三维）

sdut2193救基友记3（三维）

2024-07-17 05:36:15   220人阅读

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2193

救基友记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

通过二进制来记录是否已经得到钥匙，例如101010101 说明已经得到a,c,e,g,i钥匙。
#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;int n,m,tt;struct node{    int x,y,z;    int ans;} q[1000001];char map[21][21];int v[21][21][1001];int jx[]= {1,-1,0,0};int jy[]= {0,0,1,-1};void bfs(int xx,int yy){    memset(v,0,sizeof(v));    int s=0;    int e=0;    struct node t,f;    t.x=xx;    t.y=yy;    t.ans=0;    t.z=0;    q[e++]=t;    v[t.x][t.y][0]=1;    while(s<e)    {        t=q[s++];        if(map[t.x][t.y]==‘^‘)        {            if(t.ans<tt)            {                printf("%d\n",t.ans);                return ;            }            else            {                printf("-1\n");                return ;            }        }        for(int i=0; i<4; i++)        {            f.x=t.x+jx[i];            f.y=t.y+jy[i];            f.z=t.z;            if(f.x>=0&&f.x<n&&f.y>=0&&f.y<m&&v[f.x][f.y][f.z]==0&&map[f.x][f.y]!=‘*‘)//因为钥匙的变化，f.z也会变化，所以有钥匙和没钥匙走的是不同的路线            {                if(map[f.x][f.y]>=‘a‘&&map[f.x][f.y]<=‘j‘)                {                    int s1,s2,s3;                    s1=map[f.x][f.y]-‘a‘;                    s2=f.z;                    while(s1--)//判断之前有没有拿到过着把钥匙                    {                        s2=s2/2;                    }                    s3=s2%2;                    if(s3==0)                    {                        s1=map[f.x][f.y]-‘a‘;                        s2=1;                        while(s1--)                        {                            s2=s2*2;                        }                        f.z=f.z+s2;                    }                    f.ans=t.ans+1;                    q[e++]=f;                    v[f.x][f.y][f.z]=1;                }                else if(map[f.x][f.y]>=‘A‘&&map[f.x][f.y]<=‘J‘)                {                    int s1,s2,s3;                    s1 = map[f.x][f.y] - ‘A‘;                    s2 = f.z;                    while(s1--)                    {                        s2 /= 2;                    }                    s3 = s2 % 2;//判断之前有没有拿到钥匙                    if(s3 == 1)                    {                        f.ans = t.ans + 1;                        q[e++]=f;                        v[f.x][f.y][f.z]=1;                    }                }                else                {                    f.ans=t.ans+1;                    f.z=t.z;                    v[f.x][f.y][f.z]=1;                    q[e++]=f;                }            }        }    }    printf("-1\n");}int main(){    int x,y,j;    while(scanf("%d%d%d",&n,&m,&tt)!=EOF)    {        for(int i=0; i<n; i++)            scanf("%*c%s",map[i]);        for(int i=0; i<n; i++)        {            for(j=0; j<m; j++)            {                if(map[i][j]==‘@‘)                {                    x=i;                    y=j;                    break;                }            }            if(j!=m) break;        }        bfs(x,y);    }    return 0;}

 


联系
我们