I have used a map -> to store the time of lowest time when the Monsters can attack the square in the matrix↵
↵
Parent[x][y] -> used to store where did the prev direction when a thing reached a particular square ↵
↵
```↵
X X X X X X X X ↵
X X X L X R R X ↵
X X X X X X D X ↵
X X X X X X DR x↵
X X X X X X X X↵
```↵
↵
like this which will be used later to reconstruct the path string ↵
↵
Suggestions for more Such questions and concepts would be great.↵
↵
↵
<spoiler summary="Code : CPP">↵
↵
↵
```↵
~~~~~↵
void solve()↵
{↵
int N , M ; cin >> N >> M ;↵
↵
char g[N][M];↵
↵
pair<int,int> start , reach;↵
↵
vector<pair<int,int>> monsters ;↵
↵
vector<vector<int>> map( N , vector<int>( M , 0 ) );↵
↵
↵
auto print_map = [&]( vector<vector<char>> &map )↵
{↵
FOR( i , N )↵
{↵
FOR( j , M )↵
{↵
cout << map[i][j] << " ";↵
↵
}↵
cout << endl;↵
}↵
};↵
↵
↵
↵
FOR( i , N )↵
{↵
FOR( j , M )↵
{↵
cin >> g[i][j];↵
↵
if( g[i][j] == 'A' )↵
{↵
start = { i , j };↵
map[i][j] = 1;↵
}↵
↵
if( g[i][j] == 'M' )↵
{↵
monsters.push_back({i,j});↵
map[i][j] = 1;↵
}↵
if( g[i][j] == '#' )↵
{↵
map[i][j] = -1;↵
}↵
if( g[i][j] == '.' )↵
{↵
map[i][j] = 2005 ;↵
}↵
}↵
}↵
↵
// print_map();↵
↵
auto valid = [&]( int x , int y )↵
{↵
return x >= 0 && y >= 0 && x < N && y < M && map[x][y] != -1 ;↵
};↵
↵
↵
↵
vector<pair<int,int>> moves = { { 1 , 0 } , { -1 , 0 } , { 0 , 1 } , { 0 , -1 } } ;↵
↵
↵
↵
function<void(void)> monsters_bfs = [&]()↵
{↵
vector<vector<bool>> vis( N , vector<bool>( M , false ) );↵
↵
queue<tuple<int,int,int>> q;↵
↵
for( auto [ i , j ] : monsters )↵
{↵
q.push( { i , j , 1 } );↵
vis[i][j] = true ;↵
}↵
↵
while( !q.empty() )↵
{↵
auto [x,y,time] = q.front(); q.pop();↵
↵
for( auto [ dx , dy ] : moves )↵
{↵
if( valid(x+dx,y+dy) && !vis[x+dx][y+dy] )↵
{↵
map[x+dx][y+dy] = time + 1 ;↵
vis[x+dx][y+dy] = 1;↵
↵
q.push(make_tuple(x+dx,y+dy,time+1));↵
}↵
}↵
}↵
};↵
↵
monsters_bfs();↵
↵
// print_map();↵
↵
↵
// Source BFS -> sx , sy ↵
↵
function<char(int,int)> get = [&]( int dx , int dy )↵
{↵
if( dx == -1 ) return 'U';↵
if( dx == 1 ) return 'D';↵
if( dy == 1 ) return 'R';↵
if( dy == -1 ) return 'L';↵
↵
};↵
↵
↵
↵
bool done = false;↵
↵
vector<vector<char>> parent( N , vector<char>( M , 'X' ) );↵
↵
function<void(void)> src_bfs = [&]()↵
{↵
vector<vector<bool>> vis( N , vector<bool>( M , false ) );↵
↵
↵
↵
↵
↵
queue<tuple<int,int,int>> q;↵
↵
q.push( { start.f , start.s , 1 } );↵
↵
vis[start.f][start.s] = true ;↵
↵
while(!q.empty())↵
{↵
auto [x,y,time] = q.front(); q.pop();↵
↵
if( x == N - 1 || y == M - 1 || x == 0 || y == 0 )↵
{↵
cout << "YES" << endl;↵
reach.f = x , reach.s = y ;↵
done = true ;↵
return; ↵
}↵
↵
for( auto [ dx , dy ] : moves )↵
{↵
if( valid( x+dx,y+dy) && map[x+dx][y+dy] > time + 1 && !vis[x+dx][y+dy] )↵
{↵
↵
char go = get(dx,dy);↵
↵
// string path_new = path;↵
↵
vis[x+dx][y+dy] = true ;↵
↵
parent[x+dx][y+dy] = get(dx,dy);↵
↵
// path_new.push_back(go);↵
↵
q.push(make_tuple(x+dx,y+dy,time+1));↵
↵
↵
}↵
}↵
}↵
};↵
↵
src_bfs();↵
↵
// print_map(parent);↵
↵
↵
string ans = "";↵
↵
function<pair<int,int>(char , pair<int,int>)> go_to = [&]( char g , pair<int,int> to )↵
{↵
if( g == 'D' ) return make_pair(to.f - 1 , to.s);↵
else if( g == 'U' ) return make_pair(to.f + 1 , to.s) ;↵
else if( g == 'L' ) return make_pair(to.f , to.s + 1 );↵
else if( g == 'R' ) return make_pair(to.f , to.s - 1) ;↵
↵
};↵
↵
↵
if( done )↵
{↵
pair<int,int> r = reach;↵
↵
// cout << r.f << " " << r.s << endl;↵
↵
↵
while( r != start )↵
{↵
// cout << parent[r.f][r.s] << endl;↵
ans += parent[r.f][r.s];↵
r = go_to(parent[r.f][r.s],r);↵
// cout << r.f << " " << r.s << endl;↵
}↵
↵
cout << ans.size() << endl;↵
↵
reverse(ALL(ans));↵
↵
cout << ans << endl;↵
↵
↵
}↵
↵
↵
↵
if( not done ) cout << "NO" << endl;↵
↵
↵
}↵
~~~~~↵
...↵
</spoiler>↵
↵
↵
Parent[x][y] -> used to store where did the prev direction when a thing reached a particular square ↵
↵
```↵
X X X X X X X X ↵
X X X L X R R X ↵
X X X X X X D X ↵
X X X X X X D
X X X X X X X X↵
```↵
↵
like this which will be used later to reconstruct the path string ↵
↵
Suggestions for more Such questions and concepts would be great.↵
↵
↵
<spoiler summary="Code : CPP">↵
↵
↵
```↵
~~~~~↵
void solve()↵
{↵
int N , M ; cin >> N >> M ;↵
↵
char g[N][M];↵
↵
pair<int,int> start , reach;↵
↵
vector<pair<int,int>> monsters ;↵
↵
vector<vector<int>> map( N , vector<int>( M , 0 ) );↵
↵
↵
auto print_map = [&]( vector<vector<char>> &map )↵
{↵
FOR( i , N )↵
{↵
FOR( j , M )↵
{↵
cout << map[i][j] << " ";↵
↵
}↵
cout << endl;↵
}↵
};↵
↵
↵
↵
FOR( i , N )↵
{↵
FOR( j , M )↵
{↵
cin >> g[i][j];↵
↵
if( g[i][j] == 'A' )↵
{↵
start = { i , j };↵
map[i][j] = 1;↵
}↵
↵
if( g[i][j] == 'M' )↵
{↵
monsters.push_back({i,j});↵
map[i][j] = 1;↵
}↵
if( g[i][j] == '#' )↵
{↵
map[i][j] = -1;↵
}↵
if( g[i][j] == '.' )↵
{↵
map[i][j] = 2005 ;↵
}↵
}↵
}↵
↵
// print_map();↵
↵
auto valid = [&]( int x , int y )↵
{↵
return x >= 0 && y >= 0 && x < N && y < M && map[x][y] != -1 ;↵
};↵
↵
↵
↵
vector<pair<int,int>> moves = { { 1 , 0 } , { -1 , 0 } , { 0 , 1 } , { 0 , -1 } } ;↵
↵
↵
↵
function<void(void)> monsters_bfs = [&]()↵
{↵
vector<vector<bool>> vis( N , vector<bool>( M , false ) );↵
↵
queue<tuple<int,int,int>> q;↵
↵
for( auto [ i , j ] : monsters )↵
{↵
q.push( { i , j , 1 } );↵
vis[i][j] = true ;↵
}↵
↵
while( !q.empty() )↵
{↵
auto [x,y,time] = q.front(); q.pop();↵
↵
for( auto [ dx , dy ] : moves )↵
{↵
if( valid(x+dx,y+dy) && !vis[x+dx][y+dy] )↵
{↵
map[x+dx][y+dy] = time + 1 ;↵
vis[x+dx][y+dy] = 1;↵
↵
q.push(make_tuple(x+dx,y+dy,time+1));↵
}↵
}↵
}↵
};↵
↵
monsters_bfs();↵
↵
// print_map();↵
↵
↵
// Source BFS -> sx , sy ↵
↵
function<char(int,int)> get = [&]( int dx , int dy )↵
{↵
if( dx == -1 ) return 'U';↵
if( dx == 1 ) return 'D';↵
if( dy == 1 ) return 'R';↵
if( dy == -1 ) return 'L';↵
↵
};↵
↵
↵
↵
bool done = false;↵
↵
vector<vector<char>> parent( N , vector<char>( M , 'X' ) );↵
↵
function<void(void)> src_bfs = [&]()↵
{↵
vector<vector<bool>> vis( N , vector<bool>( M , false ) );↵
↵
↵
↵
↵
↵
queue<tuple<int,int,int>> q;↵
↵
q.push( { start.f , start.s , 1 } );↵
↵
vis[start.f][start.s] = true ;↵
↵
while(!q.empty())↵
{↵
auto [x,y,time] = q.front(); q.pop();↵
↵
if( x == N - 1 || y == M - 1 || x == 0 || y == 0 )↵
{↵
cout << "YES" << endl;↵
reach.f = x , reach.s = y ;↵
done = true ;↵
return; ↵
}↵
↵
for( auto [ dx , dy ] : moves )↵
{↵
if( valid( x+dx,y+dy) && map[x+dx][y+dy] > time + 1 && !vis[x+dx][y+dy] )↵
{↵
↵
char go = get(dx,dy);↵
↵
// string path_new = path;↵
↵
vis[x+dx][y+dy] = true ;↵
↵
parent[x+dx][y+dy] = get(dx,dy);↵
↵
// path_new.push_back(go);↵
↵
q.push(make_tuple(x+dx,y+dy,time+1));↵
↵
↵
}↵
}↵
}↵
};↵
↵
src_bfs();↵
↵
// print_map(parent);↵
↵
↵
string ans = "";↵
↵
function<pair<int,int>(char , pair<int,int>)> go_to = [&]( char g , pair<int,int> to )↵
{↵
if( g == 'D' ) return make_pair(to.f - 1 , to.s);↵
else if( g == 'U' ) return make_pair(to.f + 1 , to.s) ;↵
else if( g == 'L' ) return make_pair(to.f , to.s + 1 );↵
else if( g == 'R' ) return make_pair(to.f , to.s - 1) ;↵
↵
};↵
↵
↵
if( done )↵
{↵
pair<int,int> r = reach;↵
↵
// cout << r.f << " " << r.s << endl;↵
↵
↵
while( r != start )↵
{↵
// cout << parent[r.f][r.s] << endl;↵
ans += parent[r.f][r.s];↵
r = go_to(parent[r.f][r.s],r);↵
// cout << r.f << " " << r.s << endl;↵
}↵
↵
cout << ans.size() << endl;↵
↵
reverse(ALL(ans));↵
↵
cout << ans << endl;↵
↵
↵
}↵
↵
↵
↵
if( not done ) cout << "NO" << endl;↵
↵
↵
}↵
~~~~~↵
...↵
</spoiler>↵
↵
