import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main1189 {
public static int[][] check;
public static char[][] map;
public static int R,C,K;
public static int[] dy = {-1,0,1,0};
public static int[] dx = {0,1,0,-1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new char[R][C];
check = new int[R][C];
for(int i=0; i<R; i++) {
String s = br.readLine();
for(int j=0; j<C; j++) {
map[i][j] = s.charAt(j);
}
}
check[R-1][0] = 1;
System.out.println(go(R-1, 0));
}
public static int go(int y, int x) {
if(y == 0 && x== C-1) { //집의 좌표일시
if(K == check[y][x]) return 1;
return 0;
}
int ret = 0;
for(int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny<0 || nx < 0 || ny >=R || nx >= C ||check[ny][nx] > 0|| map[ny][nx] == 'T') continue;
check[ny][nx] = check[y][x] + 1;
ret += go(ny,nx);
check[ny][nx] = 0;
}
return ret;
}
}
'알고리즘 & 자료구조 > 백준' 카테고리의 다른 글
백준 18108 (0) | 2022.03.10 |
---|---|
백준 2231 (0) | 2022.03.07 |
백준 17298_1 (0) | 2022.03.04 |
백준 1325 (0) | 2022.03.03 |
백준 1068 (0) | 2022.03.02 |