1810

/**
 * // 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();
 * };
 */

class Solution
{
    public:
    bool t[50001];
    int grid[50001];
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    string d = "RDLU";
    int tx, ty;

    void dfs(GridMaster &master,int x,int y){
        if(master.isTarget()) tx=x,ty=y;

        t[x*201+y]=true;
        for(int i=0; i<4; i++){
            int cx = x+dx[i];
            int cy = y+dy[i];
            if(master.canMove(d[i]) && !t[cx*201+cy]){
                grid[cx*201+cy] = master.move(d[i]);
                dfs(master, cx, cy);
                grid[x*201+y] = master.move(d[(i+2)%4]);
            }
        }
    }

    int findShortestPath(GridMaster &master){
        memset(t, false, sizeof(t));
        dfs(master, 100, 100);
        bool v[50001];
        memset(v, false, sizeof(v));

        priority_queue<pair<int,int>,  vector<pair<int,int>>, greater<pair<int,int>>> q;
        q.push({0, 100*201+100});
        v[100*201+100]=true;

        while(!q.empty()){
            pair<int,int> p=q.top();
            q.pop();
            int cost = p.first;
            int x = p.second/201;
            int y = p.second%201;
            if(x==tx && y==ty) return cost;

            for(int i=0;i<4;i++){
                int cx = x+dx[i];
                int cy = y+dy[i];
                if(!v[cx*201+cy] && t[cx*201+cy]){
                    q.push({cost+grid[cx*201+cy], cx*201+cy});
                    v[cx*201+cy]=true;
                }
            }
        }
        return -1;
    }
};