1189번

1189

#include <iostream>
using namespace std;

int r, c, k;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int cnt = 0;
char map[5][5];
bool visit[5][5];

void dfs(int x, int y, int roadCnt) {
	if (x == 0 && y == c - 1) {
		if (roadCnt == k) {
			cnt++;
		}
		return;
	}

	for (int i = 0; i < 4; i++) {
		int tmpX = x + dx[i];
		int tmpY = y + dy[i];
		if (tmpX < 0 || tmpX >= r || tmpY < 0 || tmpY >= c) continue;

		if (!visit[tmpX][tmpY] && map[tmpX][tmpY] == '.') {
			visit[tmpX][tmpY] = true;
			dfs(tmpX, tmpY, roadCnt + 1);
			visit[tmpX][tmpY] = false;
		}
	}
}

int main() {
	
	cin >> r >> c >> k;
	int startX = r - 1;
	int startY = 0;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
		}
	}
	visit[startX][startY] = true;
	dfs(startX, startY, 1);
	cout << cnt;
}