Buscando a melhor grama, as vacas percorrem grade de $N$ linhas e $M$ colunas, $(2 \le N \le 100; 2 \le M \le 100)$. Farmer John observou Bessie em $(R1, C1)$ e exatamente $T$ segundos depois em $(R2, C2)$, $(0 \lt T \le 15)$. Não sabe se passou por $(R2, C2)$ antes de $T$ segundos, mas lá está no instante $T$.
Calcule o inteiro $S$, número de caminhos de $(R1, C1)$ a $(R2, C2)$ em exatamente $T$ segundos. Cada segundo vai a vizinho vertical ou horizontal, sem descansar. Não atravessa árvores.
No mapa . é espaço aberto, * árvore. Conte caminhos de $(R1, C1)$ a $(R2, C2)$ em $T$ segundos.
Entrada
- Linha 1: três inteiros $N$, $M$, $T$ separados por espaços.
- Linhas $2,\ldots,N+1$: a linha $i+1$ descreve a linha $i$ com exatamente $M$ caracteres
.ou*. - Linha $N+2$: quatro inteiros $R1$, $C1$, $R2$, $C2$ separados por espaços.
Saída
- Linha 1: inteiro $S$ numa linha.
Exemplos
Entrada 1
4 5 6 ...*. ...*. ..... ..... 1 3 1 5
Saída 1
1
Nota
O pasto tem 4 linhas e 5 colunas. Da linha 1 coluna 3 à linha 1 coluna 5 são exatamente 6 segundos.
De $(1,3)$ a $(1,5)$ em 6 segundos exatos só existe o caminho óbvio em torno das duas árvores.
Autor do problema: Aram Shatakhtsyan, 2007