找朋友

爱被打了一巴掌 2022-07-12 07:50 204阅读 0赞

#### 建议使用字符数组去建立矩阵，不要用int类型的，容易wrong answer ####

#### Problem Description ####

X，作为户外运动的忠实爱好者，总是不想呆在家里。现在，他想把死宅Y从家里拉出来。问从X的家到Y的家的最短时间是多少。

为了简化问题，我们把地图抽象为n\*m的矩阵，行编号从上到下为1 到 n，列编号从左到右为1 到 m。矩阵中’X’表示X所在的初始坐标，’Y’表示Y的位置 , ’\#’表示当前位置不能走，’ \* ’表示当前位置可以通行。X每次只能向上下左右的相邻的 ’\*’ 移动，每移动一次耗时1秒。

#### Input ####

多组输入。每组测试数据首先输入两个整数n，m(1<= n ,m<=15 )表示地图大小。接下来的n 行，每行m个字符。保证输入数据合法。

#### Output ####

若X可以到达Y的家，输出最少时间，否则输出 -1。

#### Example Input ####

3 3
    X#Y
    ***
    #*#
    3 3
    X#Y
    *#*
    #*#

#### Example Output ####

-1

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define maxn 20
    typedef struct node
    {
        int x;
        int y;
    }queue;
    char df[maxn][maxn];
    int book[maxn][maxn];
    queue q[404];
    int num[maxn][maxn];
    int n,m,a,b,flag;
    int front,rear;
    
    int bfs(int x,int y)
    {
        int i,tx,ty,k;
        int xx,yy;
        int next[4][2]={
         {-1,0},{0,1},{1,0},{0,-1}};
        book[x][y]=1;
        rear++;
        q[rear].x=x;
        q[rear].y=y;
        num[x][y]=0;
        while(front!=rear)
        {
            front++;
            xx=q[front].x;
            yy=q[front].y;
            if(df[xx][yy]=='Y')
            {
                return num[xx][yy];
            }
            for(i=0;i<4;i++)
            {
                tx=xx+next[i][0];
                ty=yy+next[i][1];
                if(tx<0||tx>=n||ty<0||ty>=m)
                    continue;
                if(df[tx][ty]!='#'&&book[tx][ty]==0)
                {
                    book[tx][ty]=1;
                    rear++;
                    q[rear].x=tx;
                    q[rear].y=ty;
                    num[tx][ty]=num[xx][yy]+1;
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        int i,j,u,v;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            flag=front=rear=0;
            memset(book,0,sizeof(book));
            memset(num,0,sizeof(num));
            for(i=0;i<n;i++)
            {
                scanf("%s",df[i]);
            }
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                {
                    if(df[i][j]=='X')
                    {
                        u=i;
                        v=j;
                        break;
                    }
                }
                if(j!=m)
                    break;
            }
            flag=bfs(u,v);
            printf("%d\n",flag);
        }
        return 0;
    }