격자 위의 로봇

면접 대비

시간 제한1초메모리 제한128 MB

요약

장애물이 있는 n x n 격자에서 왼쪽 위에서 오른쪽 아래로 오른쪽과 아래로만 이동하는 경로의 수를 2^31-1로 나눈 나머지로 세고, 경로가 없을 때 위와 왼쪽 이동까지 허용하면 도달할 수 있는지 판별한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, DFS, 행렬, 구현
정답자: 아직 제출이 없습니다

문제

격자의 왼쪽 위 칸에서 오른쪽 아래 칸까지 스스로 길을 찾아가는 로봇을 만들었다. 하지만 로봇에는 아주 단순한 논리만 들어 있어서 오른쪽과 아래쪽으로만 이동할 수 있다(어차피 목표가 그 방향에 있다).

장애물이 놓인 격자 위에 로봇을 올려놓고 지켜보다가, 로봇이 자꾸 막히는 모습에 지쳐 이런 질문이 떠올랐다. 출발점에서 도착점까지 가는 서로 다른 경로는 몇 개일까? 그리고 만약 하나도 없다면, 위쪽과 왼쪽으로도 움직일 수 있었다면 도착점에 닿을 수 있었을까?

이제 다음을 계산하는 프로그램을 작성하자. 로봇이 지나갈 수 없는 장애물이 표시된 $n \times n$ 격자가 주어질 때, 왼쪽 위 칸 $s$ 에서 오른쪽 아래 칸 $t$ 까지 오른쪽과 아래쪽으로만 이동하는 서로 다른 경로의 수를 센다. 경로의 수가 매우 커질 수 있으므로 답은 $2^{31} - 1$ 로 나눈 나머지로 출력한다. 그런 경로가 하나도 없다면, 위쪽과 왼쪽 이동까지 허용했을 때 도착점에 닿을 수 있는지 판정한다.

입력

첫째 줄에 정수 $n$ 이 주어진다( $1 \le n \le 1000$ ).

다음 $n$ 개의 줄에는 각각 $n$ 개의 문자가 주어진다. 각 문자는 .(지나갈 수 있는 칸) 또는 #(지나갈 수 없는 칸)이다. 출발 칸 $s$ (왼쪽 위)와 도착 칸 $t$ (오른쪽 아래)에는 절대 장애물이 놓이지 않는다.

출력

한 줄을 출력한다.

오른쪽과 아래쪽 이동만으로 $s$ 에서 $t$ 까지 가는 서로 다른 경로의 수를 $2^{31} - 1$ 로 나눈 나머지, 또는
오른쪽·아래쪽만으로는 갈 수 없지만 위쪽·왼쪽 이동까지 허용하면 갈 수 있는 경우 THE GAME IS A LIE, 또는
$s$ 에서 $t$ 로 가는 경로가 전혀 없는 경우 INCONCEIVABLE.

예제4

예제 1
입력
```
5
.....
#..#.
#..#.
...#.
.....
```
예상 출력
```
6
```

예제 2

입력

7
......#
####...
.#.....
.#...#.
.#.....
.#..###
.#.....

예상 출력

THE GAME IS A LIE

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