问题 H: Hz的搬砖（广搜）

青旅半醒 2022-05-27 09:58 194阅读 0赞

## 问题 H: Hz的搬砖 ##

## 题目描述 ##

Hz的学弟Hh，如果有空就会抽出时间搬砖，慢慢地攒深渊票，直到有一天，Hh想验证一下自己的欧气（欧气可以理解为人品），开始疯狂得刷深渊【时间广场】，只为那一只“清泉流响”【戒指装备】。

![pimg1939_1.jpeg][]

整个深渊地图分4\*6个小房间，我们这里为了简单化问题，假设每个房间都可以和上下左右的房间联通（边界除外）。【深渊地图如下】

![pimg1939_2.jpeg][]                                           ![pimg1939_3.jpeg][]

每次刷深渊都会从左上角房间开始，一直刷到有深渊BOSS的房间，然后退出本次深渊。每刷一个房间要消耗1点疲劳。但不幸的是有些房间的难度特别高，Hh的战斗力太弱，有些房间进去了，这场深渊之旅就被迫GG（如果Hh的战斗力小于房间的战斗力，则被迫结束）。Hz学长想知道Hh每次刷深渊最少需要消耗多少点疲劳？

## 输入 ##

第一行包括一个整数类型T，表示测试数据 （ 1 <= T <= 10）

接下来的输入表示深渊地图4\*6的房间，每个房间包括一个整数类型k，代表房间的难度【一般情况下难度k的取值范围 （1 <= k <= 100）, 深渊BOSS房间值为-1(深渊房间不会放在地图左上角)】。地图左上角的值就是Hh的战斗力，房间难度值为-1的为深渊BOSS房间。

## 输出 ##

如果Hh可以美美得刷到深渊，那么就输出消耗疲劳的最少值，否则输出”GG”。

## 样例输入 ##

4 5 1 -1 1 1

1 3 5 5 1 1

5 3 2 1 2 1

1 1 2 1 1 2

4 5 1 -1 1 1

5 5 5 5 1 1

5 3 2 1 2 1

1 1 2 1 1 2

## 样例输出 ##

##  ##

[点击打开链接][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    int f[10][10];
    int q[10][10];
    int to[4][2]={-1,0,0,1,1,0,0,-1};
    struct place
    {
        int x,y,moves;
    };
    int check(int x,int y)
    {
        if(x<0||y<0||x>=4||y>=6||q[x][y]==1||f[x][y]>f[0][0])
        {
            return 1;
        }
        return 0;
    }
    int main()
    {
        place n,m,next;
        queue<place>w;
        int t,flag;
        scanf("%d",&t);
        while(t--)
        {
            while(!w.empty())
            {
                w.pop();
            }
            memset(q,0,sizeof(q));
            flag=0;
            for(int i=0;i<4;i++)
                for(int j=0;j<6;j++)
                {
                    scanf("%d",&f[i][j]);
                }
                n.x=0;
                n.y=0;
                n.moves=1;
                q[0][0]=1;
                w.push(n);
                while(!w.empty())
                {
                    m=w.front();
                    w.pop();
                    if(f[m.x][m.y]==-1)
                    {
                        flag=1;
                        printf("%d\n",m.moves);
                        break;
                    }
                    for(int i=0;i<4;i++)
                    {
                        next.x=m.x+to[i][0];
                        next.y=m.y+to[i][1];
                        if(check(next.x,next.y))
                            continue;
                        if(f[next.x][next.y]==-1)
                        {
                            flag=1;
                            printf("%d\n",m.moves+1);
                            break;
                        }
                        next.moves=m.moves+1;
                        q[next.x][next.y]=1;
                        w.push(next);
                    }
                    if(flag==1)
                        break;
                }
                if(flag==0)
                {
                    printf("GG\n");
                }
        }
        return 0;
    }

[pimg1939_1.jpeg]: http://211.69.26.100/upload/pimg1939_1.jpeg
[pimg1939_2.jpeg]: http://211.69.26.100/upload/pimg1939_2.jpeg
[pimg1939_3.jpeg]: http://211.69.26.100/upload/pimg1939_3.jpeg
[Link 1]: http://211.69.26.100/problem.php?cid=1117&pid=7