Nightmare

绝地灬酷狼 2022-05-25 04:00 103阅读 0赞

Problem Description：

Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.  
Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.  
Here are some rules:  
1. We can assume the labyrinth is a 2 array.  
2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.  
3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.  
4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.  
5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.

6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.

Input：

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth. There are five integers which indicate the different type of area in the labyrinth: 0: The area is a wall, Ignatius should not walk on it. 1: The area contains nothing, Ignatius can walk on it. 2: Ignatius' start position, Ignatius starts his escape from this position. 3: The exit of the labyrinth, Ignatius' target position. 4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.

Output：

For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.

Sample Input：

3  
3 3  
2 1 1  
1 1 0  
1 1 3  
4 8  
2 1 1 0 1 1 1 0  
1 0 4 1 1 0 4 1  
1 0 0 0 0 0 0 1  
1 1 1 4 1 1 1 3  
5 8  
1 2 1 1 1 1 1 4  
1 0 0 0 1 0 0 1  
1 4 1 0 1 1 0 1  
1 0 0 0 0 3 0 1

1 1 4 1 1 1 1 1

Sample Output：

4  
\-1

题意：小明陷入了一个迷宫，身上还带着个炸弹，炸弹一开始的引爆时间是6分钟，他要在炸弹爆炸之前逃出迷宫，否则，他就会死翘翘，被炸弹炸飞。他在迷宫中只能通过前，后，左，右四个方向走，而且每次只能走一步，每走一步就要花1分钟。然后给你迷宫的出口位置和小明的开始位置，问小明能否顺利逃离迷宫，如果能，就输出小明最少要走几分钟，否则，输出-1.迷宫规则如下：1.迷宫是一个二阵列，2.小明不能超出迷宫的界，也不能走有石头的地方，3.若当炸弹时间为0分钟的时候，小明走到了出口处，他就无法离开迷宫，4.若小明达到炸弹休息处时，炸弹时间为0，他就无法重置炸弹时间，5.如果他到达炸弹休息处时，炸弹时间大于0，则他就可以重置炸弹时间为6。（迷宫中数字“0”代表墙，“1”代表可以走，“2”代表开始位置，“3”代表出口处，“4”代表重置炸弹）。

思路：一如既往用广搜的方法，但不同的是这道题走过的地方不能标记，他还可能会回走，所以这道题要注意只用标记起点和重置炸弹的地方，其他走过的地方不用标记，因为走不出去的地方他走着走着就自然就凉了。（为什么标记起点你们肯定都知道，而为什么标记重置炸弹的地方，因为你想呀，他 要是又走回了重置炸弹的地方就没有意义了，对吧）

My DaiMa：

#include<stdio.h>
    #include<iostream>
    #include<queue>
    #include<string.h>
    using namespace std;
    int dir[4][2] = {
       {1,0},{-1,0},{0,1},{0,-1}};
    int t,n,m,flag[10][10];
    struct position
    {
        int x,y,step,time;
    }start,eend;
    int bfs()
    {
        queue <position> Q;
        position cur,nxt;
        start.step = 0;
        start.time = 6;
        flag[start.x][start.y] = 0;
        Q.push(start);
        while(!Q.empty())
        {
            cur=Q.front();
            Q.pop();
            if(cur.x == eend.x&&cur.y == eend.y) return cur.step;
            for(int i=0;i<4;i++)
            {
                nxt.x=cur.x+dir[i][0];
                nxt.y=cur.y+dir[i][1];
                nxt.time = cur.time-1;//走一步，炸弹时间减1
                if((nxt.x>-1&&nxt.x<n)&&(nxt.y>-1&&nxt.y<m)&&flag[nxt.x][nxt.y]!=0&&nxt.time>0)
                {
                    if(flag[nxt.x][nxt.y] == 4&&nxt.time>0)//到达了重置炸弹的地方
                    {
                        nxt.time = 6;
                        flag[nxt.x][nxt.y] = 0;
                    }
                    nxt.step = cur.step+1;
                    Q.push(nxt);
                }
            }
        }
        return -1;
    }
    int main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    scanf("%d",&flag[i][j]);
                    if(flag[i][j]==2)
                    {
                        start.x=i;
                        start.y=j;
                    }
                    if(flag[i][j]==3)
                    {
                        eend.x=i;
                        eend.y=j;
                    }
                }
            }
            printf("%d\n",bfs());
        }
        return 0;
    }