ICPC Mid-Atlantic USA Regional Contest 2019

Start

2019-11-09 08:00 AKST

ICPC Mid-Atlantic USA Regional Contest 2019

End

2019-11-09 13:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -207 days 5:17:40

Time elapsed

5:00:00

Time remaining

0:00:00

Problem H
Don't Fence Me In

/problems/dontfencemein/file/statement/en/img-0001.png

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 region of the (possibly disconnected) maze.

/\
\/

This maze has only a single region fully enclosed. Removing any wall connects it to the outside.

/\..
\.\.
.\/\
..\/

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

Input

The first line has two numbers, $R$ and $C$, giving the number of rows and columns in the maze’s input description. Following this are $R$ lines each with $C$ characters, consisting only of the characters ‘/’, ‘\’, and ‘.’. Both $R$ and $C$ are in the range $1\ldots 1\, 000$.

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

Output

Output on a single line an integer indicating how many walls need to be removed so escape is possible from every region in the maze.

Sample Input 1 Sample Output 1
2 2
/\
\/
1
Sample Input 2 Sample Output 2
4 4
/\..
\.\.
.\/\
..\/
2
Sample Input 3 Sample Output 3
2 2
\/
/\
0
Sample Input 4 Sample Output 4
8 20
/\/\/\/\/\/\/\/\/\/\
\../\.\/./././\/\/\/
/./\.././\/\.\/\/\/\
\/\/\.\/\/./\/..\../
/\/./\/\/./..\/\/..\
\.\.././\.\/\/./\.\/
/.../\../..\/./.../\
\/\/\/\/\/\/\/\/\/\/
26