Solve The Maze (Codeforces 1365D)
Tags: Greedy, dsu

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.

Input: The first line contains one integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$, $$$m$$$ $$$(1 \le n, m \le 50)$$$ — the number of rows and columns in the maze.Each of the next $$$n$$$ lines contain $$$m$$$ characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.

Output: For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No"You may print every letter in any case (upper or lower).

Note: 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)$$$.

Sample Inputs:
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.

Sample Outputs:
Yes
Yes
No
No
Yes
Yes

Solution (Python):
import sys
import math
from collections import Counter, defaultdict, deque
from functools import cmp_to_key

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s)])

def invr():
    return map(int, input().split())
t = inp()
for token in range(t):
    (n, m) = invr()
    maze = []
    for blank in range(n):
        maze.append(insr())
    possible = True
    badCount = 0
    goodCount = 0
    for r in range(n):
        for c in range(m):
            if maze[r][c] == 'B':
                badCount += 1
                up = ''
                down = ''
                left = ''
                right = ''
                if r > 0:
                    up = maze[r - 1][c]
                    if up == '.':
                        maze[r - 1][c] = '#'
                if r + 1 < n:
                    down = maze[r + 1][c]
                    if down == '.':
                        maze[r + 1][c] = '#'
                if c > 0:
                    left = maze[r][c - 1]
                    if left == '.':
                        maze[r][c - 1] = '#'
                if c + 1 < m:
                    right = maze[r][c + 1]
                    if right == '.':
                        maze[r][c + 1] = '#'
                if up == 'G' or down == 'G' or left == 'G' or (right == 'G'):
                    possible = False
                    break
            elif maze[r][c] == 'G':
                goodCount += 1
        if not possible:
            break
    if maze[n - 1][m - 1] == '#' and goodCount > 0 or maze[n - 1][m - 1] == 'B':
        possible = False
    if not possible:
        print('No')
        continue
    stack = [(n - 1, m - 1)]
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[n - 1][m - 1] = True
    goodVisited = 0
    while stack:
        (r, c) = stack.pop()
        if maze[r][c] == 'G':
            goodVisited += 1
        if r > 0 and (not visited[r - 1][c]) and (maze[r - 1][c] == '.' or maze[r - 1][c] == 'G'):
            visited[r - 1][c] = True
            stack.append((r - 1, c))
        if r + 1 < n and (not visited[r + 1][c]) and (maze[r + 1][c] == '.' or maze[r + 1][c] == 'G'):
            visited[r + 1][c] = True
            stack.append((r + 1, c))
        if c > 0 and (not visited[r][c - 1]) and (maze[r][c - 1] == '.' or maze[r][c - 1] == 'G'):
            visited[r][c - 1] = True
            stack.append((r, c - 1))
        if c + 1 < m and (not visited[r][c + 1]) and (maze[r][c + 1] == '.' or maze[r][c + 1] == 'G'):
            visited[r][c + 1] = True
            stack.append((r, c + 1))
    if goodVisited == goodCount:
        print('Yes')
    else:
        print('No')

Solution (Python):
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log, sqrt
mi = lambda : map(int, input().split())
li = lambda : list(mi())
for _ in range(int(input())):
    (n, m) = li()
    finish = False
    goods = 0
    A = [[] for _ in range(n)]
    for i in range(n):
        s = input()
        for c in s:
            A[i].append(c)
    for i in range(n):
        for j in range(m):
            if A[i][j] == 'B':
                if i > 0:
                    if A[i - 1][j] == 'G':
                        print('No')
                        finish = True
                        break
                    elif A[i - 1][j] == '.':
                        A[i - 1][j] = '#'
                if i < n - 1:
                    if A[i + 1][j] == 'G':
                        print('No')
                        finish = True
                        break
                    elif A[i + 1][j] == '.':
                        A[i + 1][j] = '#'
                if j > 0:
                    if A[i][j - 1] == 'G':
                        print('No')
                        finish = True
                        break
                    elif A[i][j - 1] == '.':
                        A[i][j - 1] = '#'
                if j < m - 1:
                    if A[i][j + 1] == 'G':
                        print('No')
                        finish = True
                        break
                    elif A[i][j + 1] == '.':
                        A[i][j + 1] = '#'
            elif A[i][j] == 'G':
                goods += 1
        if finish:
            break
    if finish:
        continue
    if A[-1][-1] == 'B':
        print('No')
        continue
    elif goods == 0:
        print('Yes')
        continue
    cua = deque([(n - 1, m - 1)])
    vist = [[False for _ in range(m)] for _ in range(n)]
    while cua:
        (x, y) = cua.popleft()
        if vist[x][y]:
            continue
        vist[x][y] = True
        if A[x][y] == '#':
            continue
        if A[x][y] == 'B':
            print("Hem trobat B? No hauria d'haver passat això")
            break
        if A[x][y] == 'G':
            goods -= 1
        if x > 0 and (not vist[x - 1][y]):
            cua.append((x - 1, y))
        if x < n - 1 and (not vist[x + 1][y]):
            cua.append((x + 1, y))
        if y > 0 and (not vist[x][y - 1]):
            cua.append((x, y - 1))
        if y < m - 1 and (not vist[x][y + 1]):
            cua.append((x, y + 1))
    if goods == 0:
        print('Yes')
    else:
        print('No')

Solution (Python):
def ss(n, m, l):
    a = []
    b = []
    for i in range(n):
        for j in range(m):
            if l[i][j] == 'B':
                a.append([i, j])
            elif l[i][j] == 'G':
                b.append([i, j])
    if len(b) == 0:
        return 'Yes'
    t = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    for (x, y) in a:
        for (dx, dy) in t:
            nx = x + dx
            ny = y + dy
            if nx < n and ny < m and (nx >= 0) and (ny >= 0):
                if l[nx][ny] == 'G':
                    return 'No'
                if l[nx][ny] == '.':
                    l[nx][ny] = '#'
    if l[n - 1][m - 1] == '#':
        if len(b) == 0:
            return 'Yes'
        return 'No'
    q = [[n - 1, m - 1]]
    while q:
        q1 = []
        for (x, y) in q:
            for (dx, dy) in t:
                nx = x + dx
                ny = y + dy
                if nx < n and ny < m and (nx >= 0) and (ny >= 0) and (l[nx][ny] != '#'):
                    l[nx][ny] = '#'
                    q1.append([nx, ny])
        q = q1
    for i in range(n):
        for j in range(m):
            if l[i][j] == 'G':
                return 'No'
    return 'Yes'
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    l = []
    for i in range(n):
        l.append(list(str(input())))
    print(ss(n, m, l))