미로 연결

시간 제한5초메모리 제한512 MB

요약

슬래시와 점으로 그린 45도 회전 미로가 주어질 때, 모든 칸이 바깥과 연결되도록 제거해야 하는 벽의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 유니온 파인드, DFS, 구현
정답자: 아직 제출이 없습니다

문제

45도 회전하여 ASCII 슬래시 문자(/, \)로 그려진 직교 미로가 주어진다(아래 참고). 벽을 통과하지 않고 (연결되지 않았을 수도 있는) 미로의 모든 칸에서 바깥으로 탈출할 수 있도록 하려면, 제거해야 하는 벽의 최소 개수를 구하여라.

/\
\/

위 미로에는 완전히 둘러싸인 칸이 하나뿐이다. 어떤 벽이든 하나를 제거하면 바깥으로 탈출할 수 있다.

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

위 미로에는 둘러싸인 영역이 두 개 있다. 모든 칸을 바깥과 연결하려면 벽을 두 개 제거해야 한다.

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

위 미로에서 모든 칸에 바깥에서 접근할 수 있게 하려면 벽을 26개 제거해야 한다.

입력

첫째 줄에 미로의 행 수 r과 열 수 c가 주어진다(1 ≤ r, c ≤ 1000).

다음 r개 줄에는 각각 정확히 c개의 문자로 이루어진 문자열이 주어지며, 문자는 ‘.’, ‘/’, ‘\’ 중 하나이다. 문자 격자에서 x와 y 좌표의 합이 홀수인 칸을 홀수 칸, 짝수인 칸을 짓수 칸이라 하자. 모든 /가 홀수 칸에 있고 모든 \가 짝수 칸에 있거나, 그 반대이다.

출력

미로의 모든 칸에서 탈출이 가능하도록 제거해야 하는 벽의 최소 개수를 정수로 출력한다.

예제4

예제 1
입력
```
2 2
/\
\/
```
예상 출력
```
1
```
예제 2
입력
```
4 4
/\..
\.\.
.\/\
..\/
```
예상 출력
```
2
```
예제 3
입력
```
2 2
\/
/\
```
예상 출력
```
0
```

예제 4

입력

8 20
/\/\/\/\/\/\/\/\/\/\
\../\.\/./././\/\/\/
/./\.././\/\.\/\/\/\
\/\/\.\/\/./\/..\../
/\/./\/\/./..\/\/..\
\.\.././\.\/\/./\.\/
/.../\../..\/./.../\
\/\/\/\/\/\/\/\/\/\/

예상 출력