개발/알고리즘

백준 1189번 컴백홈 C++

daisy-day 2021. 1. 30. 01:09

문제

www.acmicpc.net/problem/1189

코드

#include<bits/stdc++.h>

using namespace std;

int n, m, dis, result, dy[4] = {-1, 0, 1, 0}, dx[4] = { 0, 1, 0, -1 }, visited[10][10];
char c[10][10];
string s;

void go(int y, int x, int& result)
{
	if (y == 0 && x == m - 1)
	{
		if (dis == visited[y][x])
		{
			result += 1;
			return;
		}
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || ny >= n || nx < 0 || nx >= m || c[ny][nx] == 'T' || visited[ny][nx])
			continue;

		visited[ny][nx] = visited[y][x] + 1;
		go(ny, nx, result);
		// 이 부분을 해주어야지 모든 경우를 탐색할 수 있다.
		visited[ny][nx] = 0;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> dis;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			c[i][j] = s[j];
		}
	}

	visited[n-1][0] = 1;
	go(n - 1, 0, result); //result 아웃변수로 해줌
	cout << result << "\n";
	return 0;
}