通过迷宫

Question

问题陈述

above是问题陈述。我知道DFS会给我TLE，但我想检查一下方法在哪里误会了。对于几个n = 1000和m = 1000的测试用例，我的答案错误。

我考虑使用DFS和递归的自下而上的方法使用回忆。 在每个单元格中，我都有4种前进的方法，我将存储最短的方法，从DP中的该特定单元格到达B。等等，我将继续继续前进。我的方法适合小测试用例，但对于大型测试用例，我想知道其中有什么问题。以下是我的代码。

#include "bits/stdc++.h"

using namespace std;

int ycor[4] = {0, -1, 0, 1};
int xcor[4] = {-1, 0, 1, 0};
char dir[4] = {'U', 'L', 'D', 'R'};

vector<vector<string>> dp;

string dfs(int x, int y, vector<vector<char>>& graph, int n, int m) {
    if (graph[x][y] == 'B') {
        return "B";
    }

    if (dp[x][y].length() != 0) {
        if (dp[x][y] == "@") {
            return "";
        }
        return dp[x][y];
    }

    graph[x][y] = '#';
    int mn = INT_MAX;
    string tillnowpath;
    for (int i = 0; i < 4; i++) {
        if (x + xcor[i] >= 0 && x + xcor[i] < n && y + ycor[i] >= 0 && y + ycor[i] < m &&
            (graph[x + xcor[i]][y + ycor[i]] == '.' || graph[x + xcor[i]][y + ycor[i]] == 'B')) {
            string str = dir[i] + dfs(x + xcor[i], y + ycor[i], graph, n, m);

            if (str[str.length() - 1] == 'B' && str.length() < mn) {
                mn = str.length();
                tillnowpath = str;
            }
        }
    }

    graph[x][y] = '.';

    if (tillnowpath == "") {
        dp[x][y] = "@";
    } else {
        dp[x][y] = tillnowpath;
    }

    return tillnowpath;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;

    cin >> n >> m;

    vector<vector<char>> graph(n, vector<char>(m));

    int x, y;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == 'A') {
                x = i, y = j;
            }
        }
    }

    dp.resize(n, vector<string>(m));
    string shpath = dfs(x, y, graph, n, m);

    shpath = shpath.substr(0, shpath.length() - 1);

    if (shpath.length() > 0) {
        cout << "YES\n" << shpath.length() << '\n' << shpath;
    } else {
        cout << "NO\n";
    }
    return 0;
}

Answer 1

######
#....#
#.##.#
#.#B.#
#.##.#
#..A.#
######

试用了四个方向的顺序，第一个通往目标的路径是

LLUUUURRRDDL

。从那里开始搜索一步，然后将路径向下延伸到撞击端的路径（在

A

的右侧）。虽然从该状态回溯，但该死端单元的

DP

值设置为

@

：这是一个问题，因为现在没有更多的可能性找到较短的路径

RUUL

.

。

快速修复是不记忆

@

。

您已经意识到，DFS并不是解决此类问题的正确方法。考虑实施A*搜索算法。