1138. Alphabet Board Path

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”], as shown in the diagram below.

We may make the following moves:

• ‘U’ moves our position up one row, if the position exists on the board;
• ‘D’ moves our position down one row, if the position exists on the board;
• ‘L’ moves our position left one column, if the position exists on the board;
• ‘R’ moves our position right one column, if the position exists on the board;
• ‘!’ adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

class Solution {
public:
    string alphabetBoardPath(string target) {
        int y = 0, x = 0;
        string res = "";
        for(auto ch : target) {
            int ny = (ch - 'a') / 5, nx = (ch-'a') % 5;

            res += string(max(0, x - nx), 'L') 
                    + string(max(0, y - ny), 'U')
                    + string(max(0, ny - y), 'D')
                      + string(max(0, nx - x), 'R')
                    + '!';
            y = ny, x = nx;
        }
        return res;
    }
};

class Solution {
    unordered_map<char, string> path[26];
    void floodfill(vector<string>& board, int y, int x, int st, string build) {
        if(0 <= y and y < board.size() and 0 <= x and x < board[y].size() and (path[st][board[y][x]] == "" or path[st][board[y][x]].length() > build.length() + 1)) {
            path[st][board[y][x]] = build + "!";

            floodfill(board, y + 1, x, st, build + 'D');
            floodfill(board, y - 1, x, st, build + 'U');
            floodfill(board, y, x - 1, st, build + 'L');
            floodfill(board, y, x + 1, st, build + 'R');
        }
    }
    void bfs(vector<string>& board, int sy, int sx, int st) {
        queue<pair<string, pair<int, int>>> q;
        path[st][board[sy][sx]] = "!";
        int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
        char dir[4] = {'U','R','D','L'};
        q.push({"",{sy,sx}});
        while(!q.empty()) {
            auto [build, pos] = q.front(); q.pop();
            auto [y, x] = pos;
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < board.size() and 0 <= nx and nx < board[ny].size() and path[st][board[ny][nx]] == "") {
                    q.push({build + dir[i], {ny, nx}});
                    path[st][board[ny][nx]] = build + dir[i] + "!";
                }
            }
        }
    }
public:
    string alphabetBoardPath(string target) {
        vector<string> board{"abcde","fghij","klmno","pqrst","uvwxy","z"};
        for(int i = 0; i < 26; i++) {
            bfs(board, i / 5, i %  5, i);
        }

        string res = path[0][target[0]];
        for(int i = 0; i < target.length() - 1; i++) {
            res += path[target[i]-'a'][target[i+1]];
        }
        return res;
    }
};