CF - Solve the Maze

Official Analysis (C++)

Explanation

The main observation is that if there is a bad person next to a good person, then it is impossible. For example, consider the following:

#####
##BG#
###..
####.

Because the good person is adjacent to the bad person, the bad person can simply just move right, and now has full access to wherever the good person can move to. It won't matter if the good person can make it, as the bad person can make it as well. Furthermore, replacing a good person with a wall is not allowed, so preventing the movement of the bad person is not allowed.

With this observation, the solution is relatively simple. Check for this adjacency, and if it exists, print "No." Otherwise, proceed by surrounding the bad people with walls. Floodfill from the end point $(N - 1,\space M - 1)$, and make sure that all the good people have been visited. You do not need to check if the bad people did not make it, as surrounding the bad people with walls is sufficient.

Implementation

Time Complexity: $\mathcal{O}(TNM)$

Copy
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 55;
char grid[mxN][mxN];
bool visited[mxN][mxN];
int rowMovement[4]{0, 1, 0, -1};
int columnMovement[4]{1, 0, -1, 0};

Copy
import java.io.*;
import java.util.*;

public class SolveTheMaze {
	static int[] rowMovement = {0, 1, 0, -1};  // right, down, left, up
	static int[] columnMovement = {1, 0, -1, 0};
	static char[][] grid;
	static boolean[][] visited;
	static int numRows;
	static int numColumns;

Copy
for _ in range(int(input())):
	n, m = map(int, input().split())

	# Stores coordinates of all good people, which we will remove as we protect.
	good_people = set()
	grid = []
	for r in range(n):
		grid.append(list(input().strip()))
		for c, char in enumerate(grid[-1]):
			if char == "G":