首页 > 代码库 > bfs

bfs

2024-07-14 16:01:11   223人阅读

                                  找朋友
Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

4-1

代码如下：

#include <stdio.h>
#include <string.h>

struct N
{
    int x; int y;
    int cnt;
}s[500], e, f;

int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};

char map[16][16];
int vt[16][16];

void bfs(int x, int y, int n, int m)
{
    int i;
    int j=0; int k=0;
    e.x = x;
    e.y = y;
    e.cnt =0;
    s[k++] = e;
    vt[e.x][e.y]=1;

    while(j < k)
    {
        e = s[j++] ;
        if(map[e.x][e.y]==‘Y‘ )
        {
            printf("%d\n", e.cnt );
            return ;
        }
        for(i=0; i<4; i++)
        {
            f.x = e.x + dx[i] ;
            f.y = e.y + dy[i] ;
            if( 0<=f.x && f.x<n && 0<=f.y && f.y<m && vt[f.x ][f.y]==0 && map[f.x][f.y]!=‘#‘ )
            {
                f.cnt = e.cnt + 1;
                s[k++] = f;
                vt[f.x][f.y] = 1;
            }
        }
    }
    printf("-1\n");

}


int main()
{
    int n, m;
    int i, j;
    int  ff;
    while(scanf("%d %d", &n, &m)!=EOF )
    {
        memset(vt, 0, sizeof(vt));

        for(i=0; i<n; i++)
        {
            scanf("%*c%s", map[i] );
        }
        //找到起点
        ff = 0;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                if(map[i][j]==‘X‘)
                {
                    ff=1;
                    break;
                }
            }
            if(j!=m)
                break;
            //if(ff=1)
            //    break;
        }
        bfs(i, j, n, m );

    }
    return 0;
}


联系
我们