주차장

시간 제한3초메모리 제한1024 MB

요약

분수대가 고정된 격자에서 다른 주차 칸을 막지 않고 왼쪽 위 출구에 도달할 수 있도록 주차 칸을 최대한 많이 배치하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산, 그래프
정답자: 아직 제출이 없습니다

문제

시는 직사각형 모양의 부지에 새 주차장을 지으려 합니다. 이 부지는 $N$ 개의 행과 $M$ 개의 열로 이루어진 격자로 볼 수 있습니다. 시장은 방문객을 늘리고 수입을 올리기 위해 정해진 칸에 분수, 우물, 수도 등 여러 종류의 분수를 설치하기로 했습니다. 나머지 칸은 차량이 다니는 곳으로, 다음 두 가지 중 하나로 정비됩니다.

주차 칸
차량이 자유롭게 지나다닐 수 있는 통행 칸

차량은 매 단계마다 북, 남, 동, 서 중 한 방향으로 인접한 칸에 이동할 수 있습니다. 주차장은 모든 주차 칸에서 언제든 왼쪽 위 칸(첫 번째 행과 첫 번째 열이 만나는 칸)에 있는 입구와 출구까지 도달할 수 있도록 지어야 합니다. 즉, 주차된 차가 다른 차의 출차를 막아서는 안 됩니다. 주차된 각 차는 다른 주차 차량을 움직이지 않고 주차장을 빠져나갈 수 있어야 합니다.

주어진 부지에 만들 수 있는 주차 칸의 최대 개수를 구하십시오.

입력

첫 줄에 부지의 행 수와 열 수를 나타내는 자연수 $N$ 과 $M$ 이 주어집니다 ( $1 \le N \le 6$ , $1 \le M \le 100$ ).

다음 $N$ 개의 줄에는 부지의 모습을 나타내는 $M$ 개의 문자가 한 줄에 하나씩 주어집니다.

'x'는 분수를 설치할 칸입니다.
'.'은 주차 칸으로 정비할 칸입니다.

출력

만들 수 있는 주차 칸의 최대 개수를 한 줄에 출력하십시오.

힌트

네 번째 예시에 대한 설명입니다. 주차 칸을 배치하는 한 가지 방법은 다음과 같습니다(P는 주차 칸).

.PPPx
....x
.Px.P
PxP.x

예제4

예제 1
입력
```
3 3
...
.x.
...
```
예상 출력
```
2
```
예제 2
입력
```
3 3
...
..x
...
```
예상 출력
```
4
```
예제 3
입력
```
3 6
.x..x.
..x.x.
......
```
예상 출력
```
3
```
예제 4
입력
```
4 5
....x
....x
..x..
.x..x
```
예상 출력
```
7
```