原题大意

走迷宫,用数组表示迷宫,0表示墻,1表示空房间,2表示起点,3表示终点,4表示可重新设置时间的房间.限时6s,每走一步算1s,走到4房间后可以将时间重新设为6s.

算法分析

bfs检索,从2开始,若时间用光后没能走出,输出-1,否则输出最少的步数.
注意:当走过任何一个4号房间后,其重新设置时间的功能应当取消,否则走不出来.

程序代码

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
const int N=8;
int dx[]={0,0,1,-1};//8个方向 
int dy[]={1,-1,0,0};
int labyrinth[N][N];//记录迷宫 
int used[N][N];//记录房间4是否被走过 
int row,col;//迷宫实际占用的行与列 
int flag=0;//能否成功走出的标志 
struct Point{
    int x,y;
    int time;//记录剩余时间 
    int len; //走的步数,实际是已用的时间 
};
Point from,to;//起点与终点 
void bfs()
{
    queue<Point> q;
    Point a=from;
    q.push(a);
    while(!q.empty())
    {
        Point tmp;
        tmp=q.front();
        q.pop();
        if(tmp.x==to.x&&tmp.y==to.y&&tmp.time>=1)//到达终点且时间够用 
        {
            to.len=tmp.len;
            flag=1;
            break;
        }
        for(int i=0;i<4;i++)
        {
            Point k;
            k.x=tmp.x+dx[i];
            k.y=tmp.y+dy[i];
            k.time=tmp.time-1;
            k.len=tmp.len+1;
            if(k.time<=0)             //如果时间不够 
                continue;
            if(k.x<0||k.x>=row||k.y<0||k.y>=col)    continue;//边界处理 
            if(labyrinth[k.x][k.y]==0)    continue;//撞墙舍去 
            if(labyrinth[k.x][k.y]==4&&!used[k.x][k.y])//如果进入房间4,且是第一次走 
                {
                    k.time=6;
                    used[k.x][k.y]=1;
                }
            q.push(k);
        }
    }
    if(!flag)
        to.len=-1;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        memset(used,0,sizeof(used));
        flag=0;
        scanf("%d%d",&row,&col);
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                scanf("%d",&labyrinth[i][j]);
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
            {
                if(labyrinth[i][j]==2)//记录起点 
                {
                    from.x=i;
                    from.y=j;
                    from.time=6;
                    from.len=0;
                }
                if(labyrinth[i][j]==3)//记录终点 
                {
                    to.x=i;
                    to.y=j;
                }
            }
        bfs();
        printf("%d\n",to.len);
    }
    return 0;
}