Shortest path through a labyrinth: not always getting correct result

I am trying to solve the CSES challenge Labyrinth:

Labyrinth

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input

The first input line has two integers 𝑛 and 𝑚: the height and width of the map.

Then there are 𝑛 lines of 𝑚 characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

Constraints

• 1 ≤ 𝑛, 𝑚 ≤ 1000

Example

Input:

5 8
########
#.A#...#
#.##.#B#
#......#
########

Output:

YES
9
LDDRRRRRU

I know DFS would give me a time out on large inputs, but I get a wrong output for a few larger test cases and wonder what my mistake is.

Here is my code:

#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;
}

This is using DFS and a recursive bottom up approach using memoization. At each cell I have 4 ways to move ahead and I will store the shortest way to get to B from that particular cell in DP. And so I will continue moving on. My approach works fine for the small test cases I tried with, but it failed for larger ones.

Here is an input for which I get a wrong output:

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

Expected output:

YES
45
RUUUUUUUULLUURRUULLLLDDLLLLUULLLLUULLDDDDLLDD

But my program gives:

YES
59
LLLUULLLLLLUULLDDLLUULLLLUUUUUUUUUUUUUURRDDRRRRDDLLDDDDLLDD

What's wrong in my approach?

The problem is that by setting some DP values to "@", you block a potential alternative road to the target that might be shorter than the paths that were already tried so far.

Here is an example input where that happens:

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

Given the order in which the four directions are tried, the first path to the target that is found is LLUUUURRRDDL. From there the search backtracks one step, and then extends the path downward where it hits a dead end (at the right side of A). While backtracking from that state, the DP value for that dead end cell is set to @: this is a problem, as now there is no more possibility to find the shorter path RUUL.

The quick fix is to not memoize @.

As you already realised, DFS is not the right approach for this type of problem. Consider implementing an A* search algorithm.