内存:128  时间:1

题目描述

共享单车走进烟台,小明决定尝试。小明启动共享单车app,轻松地找到附近的单车。那么问题来了,到最近的那辆单车,小明大约要走多少米呢?

现在简化问题。将地图设定成一个由100米*100米的像素块组成的二维平面区域。如果一个方块内有单车,则像素块显示为字符“x”;如果此方块内是可以通行的路,则显示为“.”;再如果方块是建筑物,则显示为“*”,建筑物不能通行。

小明在地图上的位置显示为“o”,可以朝,“上”、“下”、“左”,“右”,“左上”,“左下”,“右上”,“右下”八个方向走。下图所示为一个小明站在像素方块O,如果小明向右走到X,则走100米;如果向右上走,则走141米(不需要开方)。

假设小明和单车都在方块的中央。现在给出 T 幅根据以上规则建立的地图,地图行数和列数分别为 n 和 m,请分别估算小明要走多少米才能到最近的单车?

如果计算中出现小数,那么直接舍弃。最后的输出的结果为整型。
给出的地图中至少有一辆单车,如果最终无法到达单车的位置,输出-1。

输入

第1行,T,表示下面有 T 组测试数据
对于每组测试数据
(1)第1行,n和m ,表示地图的大小;
(2)第2行开始,给出具体的地图 。

输出

T行数据
每行1个整数,表示问题的解

样例输入

2
3 8
…..x..
.o…x..
……..
8 10
.***……
.***……
.***..x…
……….
…..*****
..o..*****
…….x..
…*******

样例输出

400
523

提示

代码如下

#include<iostream>
#include<cstdio>
using namespace std;
struct rude
{
    int x,y,rlength;
}a[5000];
int b[110][110],x1,y1;
int dx[]={-1,0,1,0,-1,1,1,-1};
int dy[]={0,1,0,-1,1,1,-1,-1};
void bfs(int n,int m)
{
    int head=0,rear=0;
    int x2,y2;
    while(head<=rear)
    {
        for(int i=0;i<8;i++)
        {
            x2=a[head].x+dx[i];
            y2=a[head].y+dy[i];
            if(x2>0&&x2<=n&&y2>0&&y2<=m&&(b[x2][y2]==0||b[x2][y2]==2))
            {
                rear++;
                a[rear].x=x2;
                a[rear].y=y2;
                if(i>=4)
                    a[rear].rlength=a[head].rlength+141;
                else
                    a[rear].rlength=a[head].rlength+100;
                if(b[x2][y2]==2)
                {
                    printf("%d
",a[rear].rlength);
                    return ;
                }
                b[x2][y2]=1;
            }
        }
        head++;
    }
    printf("-1
");
}
int main()
{
    int n,m,p;
    cin>>p;
    char ch;
    for(int s=1;s<=p;s++)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
        {
            cin>>ch;
            if(ch=='o')
            {
                x1=i;
                y1=j;
            }
            else if(ch=='x')
                b[i][j]=2;
            else if(ch=='.')
                b[i][j]=0;
            else if(ch=='*')
                b[i][j]=1;
        }
        a[0].x=x1;
        a[0].y=y1;
        a[0].rlength=0;
        bfs(n,m);
    }
}

代码来源于互联网,仅供参考!