(https://codeforces.com/contest/1365/problem/D)
Probably the easiest problem D in recent times.
In problem, there is a grid(n*m) filled with either ‘.’ , ‘#’, ’G’, ’B’ denoting blank cell, wall, a good person and a bad person respectively. (n*m)th cell is only the escape, we need to build walls allowing only good people to escape from the greed.
Idea:
A)if n*m cell is already occupied by a bad person, obviously we can’t stop him escaping, hence print NO.
B) The only way to block a bad person form escaping is by building the walls in all four directions surrounding the cell, in this process if one the surrounding grid occupied by a good person, then obviously we can not build walls, confining the bad person in the grid (Why ? think is trivial!)
if all the bad people were trapped by building walls, now check if there is a path for every good person, simple dfs would do this, starting from n*m th cell mark all connected cells true if they can be visited.
Check out the code.
