Maze Connect

This problem was used in the following GFU competitions:

• GFU 2024 D1 Q9

Given an orthogonal maze rotated 45 degrees and drawn with forward and backward slash characters (see below), determine the minimum number of walls that need to be removed to ensure it is possible to escape outside of the maze from every square of the (possibly disconnected) maze.

/\

\/

This maze has only a single square fully enclosed. Removing any wall will connect it to the outside.

/\..

\.\.

.\/\

..\/

This maze has two enclosed areas. Two walls need to be removed to connect all squares to the outside.

The first line will contain a single integer t that indicates the number of test cases that follow. The next t test cases will begin with two integers, R and C, giving the number of rows and columns in the maze’s input description. Following this will be R lines each with C characters, consisting only of the characters ‘/’, ‘\’, and ‘.’ Both R and C are in the range 1 ... 1000, inclusive.

Define an odd (even) square as one where the sum of the x and y coordinates is odd (even). Either all forward slashes will be in the odd squares and all backslashes in the even squares, or vice versa.

For each test case, output a single line containing an integer indicating how many walls need to be removed so escape is possible from every square in the maze.