My Solution for CSES - Monsters - Suggestions for Improvement are highly appreciated
Difference between en1 and en2, changed 38 character(s)
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.↵


<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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English samadeep 2023-09-20 06:59:47 38
en1 English samadeep 2023-09-20 06:58:04 4242 Initial revision (published)