BOJ 6175 Cow Travelling

문제 링크:

문제 내용

$N$행 $M$열의 사각 격자의 각 칸에는 풀이 자라 있거나 나무가 자라 있습니다.

베시가 시간 0에 $(R_1, C_1)$에 있었다가 시간 $T$에 $(R_2, C_2)$에 있었다고 할 때, 베시가 거쳐갔을 수 있는 서로 다른 경로의 수를 구하세요. $(R, C)$는 위쪽에서부터 $R$번째 행, 왼쪽에서부터 $C$번째 열에 있는 칸을 의미합니다.

베시는 매 시간마다 상하좌우로 이웃한 칸 중 하나로 이동할 수 있습니다. 나무가 있는 칸으로는 이동할 수 없습니다. 이동 중에 같은 칸을 여러 번 방문했을 수도 있습니다.

입력

첫 번째 줄에 $N$, $M$, $T$가 주어집니다. ($2 \le N \le 100$, $2 \le M \le 100$, $1 \le T \le 15$)

다음 $N$줄에 걸쳐서 사각 격자의 상태가 주어집니다. .인 칸은 풀이 있는 칸, *인 칸은 나무가 있는 칸입니다.

그 다음 줄에는 $R_1$, $C_1$, $R_2$, $C_2$가 주어집니다. ($1 \le R_1, R_2 \le N$, $1 \le C_1, C_2 \le M$)

출력

문제의 답을 출력합니다.

문제 풀이