[C++] 백준 문제풀이 (BackTracking) 1189번 컴백홈

 

 

https://www.acmicpc.net/problem/1189

1189번: 컴백홈

 

 

 

#include <bits/stdc++.h>
// [C++] 백준 문제풀이 (BackTracking)

int r, c, k;
std::string map[5];
int ret;
const int dy[] = {0, 0, -1, 1};
const int dx[] = {-1, 1, 0, 0};
bool visit[5][5];

void dfs(int y, int x, int dist){
	visit[y][x] = true;
	if (y == 0 && x == c - 1){
		if (dist == k) ++ret;
		return;
	}

	for (int dir = 0; dir < 4; ++dir){
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
		if (visit[ny][nx]) continue;
		if (map[ny][nx] == 'T') continue;
		dfs(ny, nx, dist + 1);
		visit[ny][nx] = false;
	}
}


int main(int argc, char *argv[])
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> r >> c >> k;

	for (int i = 0; i < r; ++i){
		std::cin >> map[i];
	}

	dfs(r - 1, 0, 1);

	std::cout << ret << "\n";
	return 0;
}