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 D 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.
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;
} ~~~~~ ...
