HE April Circuits 2B - Bear and Walk ( Left / RIght hand rule )

https://www.hackerearth.com/april-circuits/approximate/2b-bear-and-walk-1/
It is not difficult to come up to the maze solving left / right hand rule.
www.youtube.com
Since the path is connected, it will work. However, there are several different kinds of implementations, at first I tried moving clockwise / counterclockwise or so. But it failed for some reason I was not able to debug.
Here's another good way to implement, mark each visited cell as a wall ( as the description provides ), and mark all 8 neighbour cells as "should try to visit", and only visit those that are not wall but in the list of "should try to visit", it will somehow work like the left hand rule.

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 1e3 + 3;
const int MAXN = 1e4 + 4;
typedef pair< int, int > pii;

const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
const int dy[] = { 1, 0, -1, 0, -1, 1, -1, 1 };

int cd[ 256 ];
char dc[ 4 ] = { 'R', 'D', 'L', 'U' };

string s;

bool dfs( pii st, const pii ed, char pmv, const set< pii > &wall, const set< pii > &path, set< pii > &vis ){
    if( st == ed ){
        cout << pmv; // previous move
        return true; // succeed
    }
    vis.insert( st );
    for( int di = 0; di < 4; ++di ){
        int nx = st.first + dx[ di ];
        int ny = st.second + dy[ di ];
        if( vis.count( pii( nx, ny ) ) ) continue;
        if( wall.count( pii( nx, ny ) ) ) continue;
        if( !path.count( pii( nx, ny ) ) ) continue;
        if( dfs( pii( nx, ny ), ed, dc[ di ^ 2 ], wall, path, vis ) ){
            cout << pmv;
            return true;
        }
    }
    return false;
}

void solve(){
    pii p; // start
    set< pii > wall, should_try; // cannot / can be stepped upon
    p = pii( 0, 0 );
    for( int i = 0; i < s.size(); ++i ){
        p.first += dx[ cd[ s[ i ] ] ];
        p.second += dy[ cd[ s[ i ] ] ];
        for( int di = 0; di < 8; ++di ){
            int nx = p.first + dx[ di ];
            int ny = p.second + dy[ di ];
            should_try.insert( pii( nx, ny ) );
        }
        wall.insert( p );
    }
    wall.erase( pii( 0, 0 ) );
    wall.erase( p );
    should_try.insert( pii( 0, 0 ) );
    should_try.insert( p );
    set< pii > vis;
    if( !dfs( pii( 0, 0 ), p, '\n', wall, should_try, vis ) )
        cout << "IMPOSSIBLE\n";
}

int main(){
    cd[ 'R' ] = 0; // 00
    cd[ 'L' ] = 2; // 10 -> put them in binary notation, 
    cd[ 'U' ] = 3; // 11 -> can see that opposite directions can be transitioned by XOR 10
    cd[ 'D' ] = 1; // 01
    ios::sync_with_stdio( false );
    int T; cin >> T;
    while( T-- ){
        cin >> s;
        solve();
    }
    return 0;
}