CF1365D Solve The Maze

Vivek has encountered a problem. He has a maze that can be represented as an $ n \times m $ grid. Each of the grid cells may represent the following: - Empty — '.' - Wall — '\#' - Good person — 'G' - Bad person — 'B' The only escape from the maze is at cell $ (n, m) $ . A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through. Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions. It is guaranteed that the cell $ (n,m) $ is empty. Vivek can also block this cell.

N/A

N/A

For the first and second test cases, all conditions are already satisfied. For the third test case, there is only one empty cell $ (2,2) $ , and if it is replaced with a wall then the good person at $ (1,2) $ will not be able to escape. For the fourth test case, the good person at $ (1,1) $ cannot escape. For the fifth test case, Vivek can block the cells $ (2,3) $ and $ (2,2) $ . For the last test case, Vivek can block the destination cell $ (2, 2) $ .