백준 1189번 컴백홈 ( C++ )

문제

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

 

해설

백트래킹을 이용한 간단한 탐색 문제

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int r, c, k, visited[7][7], ret;
char mp[7][7];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
 
void dfs(int y, int x, int cnt)
{
  if (cnt == k)
  {
    if (y == 0 && x == c - 1)
    {
      ret++;
    }
    return;
  }
 
  for (int i = 0; i < 4; i++)
  {
    int ny = y + dy[i];
    int nx = x + dx[i];
    if (ny >= 0 && ny < r && nx >= 0 && nx < c && !visited[ny][nx] && mp[ny][nx] == '.')
    {
      visited[ny][nx] = 1;
      dfs(ny, nx, cnt + 1);
      visited[ny][nx] = 0;
    }
  }
}
 
int main()
{
  scanf("%d %d %d", &r, &c, &k);
  for (int i = 0; i < r; i++)
  {
    scanf("%s", mp[i]);
  }
 
  visited[r - 1][0] = 1;
  dfs(r - 1, 0, 1);
  printf("%d", ret);
}