1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *   public:
 *     bool canMove(char direction);
 *     int move(char direction);
 *     boolean isTarget();
 * };
 */
 
 typedef std::pair<int, int> PII;
 typedef std::pair<int, PII> PIPII;
 
 const int INF = 0x3fff'ffff;

class Solution {
    std::string DIRS = "UDLR";
    std::string BDIR = "DURL";
    const int dx[4] = { -1, 1, 0, 0 };
    const int dy[4] = { 0, 0, -1, 1 };
    
    int grid[201][201] = { 0 };
    bool visited[201][201] = { 0 };
    PII start = { 100, 100 };
    PII target = { -1, -1 };
    
    void dfs(int x, int y, GridMaster& master) {
        if (master.isTarget()) {
            target.first = x;
            target.second = y;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            char dir = DIRS[i];
            char bdr = BDIR[i];
            if (!visited[xx][yy] && master.canMove(dir)) {
                grid[xx][yy] = master.move(dir);
                dfs(xx, yy, master);
                grid[x][y] = master.move(bdr);
            }
            else if (!visited[xx][yy]) {
                grid[xx][yy] = -1;
            }
        }
    }
public:
    int findShortestPath(GridMaster& master) {
        std::vector<std::vector<int>> dist(201, std::vector<int>(201, INF));
        std::priority_queue<PIPII, std::vector<PIPII>, std::greater<PIPII>> pq;
        dfs(start.first, start.second, master);
        if (target.first == -1) {
            return -1;
        }
        pq.push({0, start});
        dist[start.first][start.second] = 0;
        while (!pq.empty()) {
            int d = pq.top().first;
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            pq.pop();
            if (d > dist[x][y]) {
                continue;
            }
            for (int i = 0; i < 4; ++i) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (!visited[xx][yy] || grid[xx][yy] < 0) {
                    continue;
                }
                if (dist[xx][yy] > dist[x][y] + grid[xx][yy]) {
                    dist[xx][yy] = dist[x][y] + grid[xx][yy];
                    pq.push({dist[xx][yy], {xx, yy}});
                }
            }
        }
        if (dist[target.first][target.second] != INF) {
            return dist[target.first][target.second];
        }
        return -1;
    }
};