当前位置：首页 > news >正文

hrbust0J月赛myj的尘歌壶—dfs（走迷宫）

news 来源：原创 2024/9/21 17:44:36

Description

最近myj沉迷原神无法自拔，在原神的游戏系统中，有一个叫做尘歌壶的家园系统，你可以在里面放置各种物品

但是myj是一个急功近利的人，为了白嫖到奖励，不惜一切代价，而这一行为导致他的尘歌壶里面一片混乱

某一天，他在正常游戏的时候，发现自己在尘歌壶里面迷路了，而他发现他的尘歌壶可以转化为一个n*m的简单二维图，其中1表示障碍物，0表示空地。若你位于一格0上，那么你可以移动到相邻4格中的任意一格0上

现在myj给你他所在的位置，和他想去的位置，你能帮他找找是否存在一条路径使他在混乱的尘歌壶中走到目标位置吗？

Input

第一行一个数字T，表示有T组测试数据

对于每一组数据：第一行包含两个整数n，m，表示myj给你的地图大小有n行m列

接下来有n行由01构成的字符串，每行字符串有m个字符，若当前字符为1，表示不可以通过。0表示可以正常通过

最后一行包含四个整数sx，sy，ex，ey，分别表示myj现在所在的点坐标，和终点的点坐标

n,m≤500，T≤10，数据保证起点和终点不是障碍物，且对于所有数据而言，n*m的总和不大于1e7

Output

如果myj能够顺利到达，输出YE5

否者输出N0

Sample Input

4
3 3
001
100
110
1 1 3 3
3 3
001
111
110
1 1 3 3
3 3
000
111
110
1 1 3 3
4 4
1001
1101
1101
1000
1 3 4 4

Sample Output

YE5

Hint

输出建议直接复制题目

每输出一行都应该有一个换行符

行末没有多余空格

迷宫左上角坐标为（1，1），右下角为（n，m）

提示：可以参考马老师讲过的走迷宫代码，注意复杂度！

我的代码：

#include<bits/stdc++.h>
using namespace std;
int sx, sy, ex, ey;
int n, m;
char arr[510][510];
int dir[4][2] = {{0, -1},{-1,0},{0,1},{1,0}};
bool vis[510][510];
bool in(int x, int y) {
    return x >= 1 && x <=n&& y >= 1 && y <=m;
}
bool dfs(int x,int y) {
    vis[x][y] = true;
    //终止条件
    if (x == ex && y == ey) {
        return true;
    }
    for (int i = 0;i < 4;i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && !vis[tx][ty] && arr[tx][ty] != '1') {
            if (dfs(tx, ty)) return true;
        }
    }
    return false;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(arr, '\0', sizeof(arr));
        memset(vis, false, sizeof(vis));
        cin >> n >> m;
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                cin >> arr[i][j];
            }
        }
        cin >> sx >> sy >> ex >> ey;
        bool ans = dfs(sx, sy);
        if (ans) {
            cout << "YE5" << endl;
        }
        else cout << "NO" << endl;
    }
    return 0;
}

提交结果为wrong answer，测试了多个样例，都是正确结果，暂时把问题放在这里；往以后能解决