개발/알고리즘
백준 1189번 컴백홈 C++
daisy-day
2021. 1. 30. 01:09
문제
코드
#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;
}