汤圆の拯救计划

Dear 丶 2022-07-12 12:28 112阅读 0赞

#### Problem Description ####

又到了汤圆星球一年一度的汤圆节了，但是大魔王却过来把汤圆公主抓走了Σ( ° △ °|||)︴  
  
身为汤圆骑士的QAQ蒟蒻自然而然的肩负着拯救汤圆的使命  
  
QAQ蒟蒻经历了千辛万苦（并没有）之后，来到了大魔王的城堡，根据情报，汤圆公主就被大魔王放在城堡内，然后QAQ蒟蒻发现自己是一个路  
  
痴，所幸的是他拿到了大魔王的城堡的地图，而且在这上面标注了自己和汤圆公主的位置，那么问题来了，聪明的你能帮他计算出需要多少单位  
  
的时间来赶到汤圆公主的位置吗？  
  
  
Ps：QAQ蒟蒻每一次都可以移动到相邻的非墙的格子中，每次移动都要花费1个单位的时间  
  
有公共边的格子定义为相邻

#### Input ####

一开始为一个整数T代表一共有T组数据  
  
每组测试数据的第一行有两个整数n,m (2<=n,m<=300)  
  
接下来的n行m列为大魔王的迷宫，其中  
  
’\#’为墙壁，‘\_‘为地面  
  
A代表QAQ蒟蒻，O代表汤圆公主:

#### Output ####

一组数据输出一个整数代表从QAQ蒟蒻到汤圆的位置的最短时间  
  
如果QAQ蒟蒻不能到达汤圆的位置，输出-1

#### Example Input ####

2
    3 3
    __A
    _##
    __O
    2 2
    A#
    #O

#### Example Output ####

6
    -1

#### Hint ####

#### Author ####

QAsQ

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int jx[] = {0, 1, 0, -1};
    int jy[] = {1, 0, -1, 0};
    char map[3333][3333];
    int visit[3333][3333];
    struct node
    {
        int x, y, c;
    }q[99999], t, f;
    void bfs(int x, int y, int n, int m)
    {
        int s = 0, e = 0, i;
        t.x = x;
        t.y = y;
        t.c = 0;//因为把她放在q[e++] = t 的后面导致我改了n次
        visit[t.x][t.y] = 1;
        q[e++] = t;
        while(s < e)
        {
            t = q[s++];
            if(map[t.x][t.y] == 'O')
            {
                printf("%d\n", t.c);
                return;
            }
            for(i = 0; i < 4; i++)
            {
                f.x = t.x + jx[i];
                f.y = t.y + jy[i];
                if(f.x >= 0 && f.x < n && f.y >= 0 && f.y < m && !visit[f.x][f.y] && map[f.x][f.y] != '#')
                {
                    f.c = t.c + 1;
                    visit[f.x][f.y] = 1;
                    q[e++] = f;
                }
            }
        }
        printf("-1\n");
    }
    int main()
    {
        int n, m, t, i, j;
        scanf("%d", &t);
        while(t--)
        {
            memset(map, 0, sizeof(map));
            memset(visit, 0, sizeof(visit));
            scanf("%d%d", &n, &m);
            for(i = 0; i < n; i++)
            {
                scanf("%s", map[i]);
            }
            for(i = 0; i < n; i++)
            {
                for(j = 0; j < m; j++)
                {
                    if(map[i][j] == 'A')
                    {
                        break;
                    }
                }
                if(j != m)
                    break;
            }
            bfs(i, j, n, m);
        }
        return 0;
    }