Replace the empty cells with walls if they are adjacent to bad cells

Take the escape $$$(n,m)$$$ as the source node to perform depth-first-search (DFS) traversal.

Here’s the step-by-step process:

1. Represent the graph in a grid as a graph representation.
2. Identify all the good, bad, and empty cells.
3. Replace the empty cells with walls if they are adjacent to bad cells.
4. Initialize a visited set to track visited nodes.
5. Take the cell $$$(n,m)$$$ as a source node and perform a depth-first search (DFS) traversal.
6. Once the traversal is finished, check if all good cells exist in the visited set and none of the bad cells exist in the visited set.
7. If some (one or more) good cells do not exist in the visited set, it means we can’t traverse to all the good cells, and all of the good people can’t escape.
8. If some (one or more) bad cells exist in the visited set, it means we can’t block all bad cells, and they can escape.

Time Complexity: $$$O(N * M)$$$, where $$$N$$$ is the number of rows and $$$M$$$ is the number of columns in the maze.

Space Complexity: $$$O(N * M)$$$

def inBound(row, col, n, m, visited, graph):
    return 0 <= row < n and 0 <= col < m and (row, col) not in visited and graph[row][col] != '#'

def main():
     for _ in range(int(input())):
        n, m = map(int, input().split())
        graph = []

        for _ in range(n):
            graph.append(list(input()))
        
        direc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        good, bad, empty = [], [], []

        # Find the good, bad and empty cells
        for row in range(n):
            for col in range(m):
                if graph[row][col] == 'G':
                    good.append((row, col))
                elif graph[row][col] == 'B':
                    bad.append((row, col))
                elif graph[row][col] == '.':
                    empty.append((row, col))

        # Replace the empty cells with walls if they are adjacent to bad cells
        for row, col in empty:
            for i, j in direc:
                _row, _col = row + i, col + j
                if 0 <= _row < n and 0 <= _col < m and graph[_row][_col] == 'B':
                    graph[row][col] = '#'
                    break 

        # Check if the good cells are reachable and the bad cells are not reachable
        stack = [(n - 1, m - 1)]
        visited = set()
        while stack:
            row, col = stack.pop()
            if not inBound(row, col, n, m, visited, graph):
                continue
            visited.add((row, col))
            for i, j in direc:
                _row, _col = row + i, col + j
                stack.append((_row, _col))

        ans = 'Yes'
        for cell in good:
            if cell not in visited:
                ans = 'No'
                break
        
        for cell in bad:
            if cell in visited:
                ans = 'No'
                break

        print(ans)

if __name__ == '__main__':
    main()

To begin with, let's understand why the string will return to its original form. In fact, the graph that the permutation sets consists of simple cycles and it turns out that after a certain number of operations, each character will return to its place.

Consider each cycle as a string that is cyclically shifted every turn. It may seem that the answer is — lcm (the smallest common multiple) of the cycle lengths, but to become equal to the initial string, it is not necessary to go through the entire cycle. We can calculate the length of the minimum suitable shift $$$k_j$$$ in $$$O(len)$$$ using built in function. Note that after $$$k_j$$$ operations, the cycle will return to its original form and this will happen again after $$$k_j$$$.

operations.

The answer will be lcm of all $$$k_j$$$, since each cycle individually comes to its original form after the number of operations is a multiple of its $$$k_j$$$.

import sys
from math import gcd
 
def solve():
	# Read input for the number of elements, string, and array of integers
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	a = list(map(int, sys.stdin.readline().split()))
 
	lcm = 1
	vis = [0] * n
	for i in range(n):
    	if vis[i]:
        	continue
    	cur = []
    	ind = i
    	# Traverse the cycle starting from current index
    	while not vis[ind]:
        	cur.append(s[ind])
        	vis[ind] = 1
        		ind = a[ind] - 1
    	# Create a search string by repeating current cycle twice
    	search = "".join(cur + cur)
    	# Remove the first character (repetition), if we dont remove it the answer will always be 0
    	search = search[1:]  
    	# Find the starting index of the cycle
    	index = search.find("".join(cur)) + 1  
    	lcm = (lcm* index) // gcd(lcm, index)
	return lcm
 
if __name__ == "__main__":
 
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
    	# Call solve() for each test case and print the result
    	result = solve()
    	print(result)