2018年东北农业大学春季校赛 D wyh的迷宫【搜索】

链接：https://www.nowcoder.com/acm/contest/93/D
来源：牛客网

题目描述

给你一个n*m的迷宫，这个迷宫中有以下几个标识：

s代表起点

t代表终点

x代表障碍物

.代表空地

现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。

输入描述:

输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点

输出描述:

对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO

输入例子:

1

3 5

s...x

x...x

...tx

输出例子:

YES

-->

示例1

输入

1

3 5

s...x

x...x

...tx

输出

YES
【分析】：判断地图可达性。可以DFS搜索看是否可以到达终点，某点a[x][y] == 't'（终点） or v[ex][ey]==1（终点坐标） 就说明可以，输出YES
【代码】：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 550

int t;

char a[N][N];

int dx[] = {, , -, };

int dy[] = {, -, , };

int v[N][N];

int f;

int n, m;

int ok(int tx, int ty)

{

    if(tx>= && tx<n && ty>= && ty<m && a[tx][ty]!='x' && v[tx][ty] == )

        return ;

    else return ;

}

void dfs(int x, int y)

{

    v[x][y] = ;

    if(a[x][y] == 't'){

        f = ;

        return ;

    }

    for(int i=; i<; i++){

        int x1 = x + dx[i];

        int y1 = y + dy[i];

        if(ok(x1,y1))

            dfs(x1,y1);

    }

}

int main()

{

    int t, sx, sy;

    scanf("%d", &t);

    while(t--) {

        f = ;

        scanf("%d %d", &n, &m);

        memset(v, , sizeof(v));

        for(int i = ; i < n; i++) {

            scanf("%s", a[i]);

        }

        for(int i = ; i < n; i++) {

            for(int j = ; j < m; j++) {

                if(a[i][j] == 's') {

                    sx = i;

                    sy = j;

                    break;

                }

            }

        }

        dfs(sx, sy);

        if(f == )

            printf("YES\n");

        else

            printf("NO\n");

    }

    return ;

}

/*

1

3 5

s...x

x...x

...tx

*/

dfs

巴特西

2018年东北农业大学春季校赛 D wyh的迷宫【搜索】

题目描述

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

最新文章

热门文章