백준 15684번 사다리 조작 ( C++ )

문제

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

 

해설

반복문을 돌며 사다리타기를 하는 방법을 구상해야함

2차원 배열을 통해 가로선의 위치를 기록하는 방식

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, m, h, ret = 7, a, b;
int visited[34][14];
 
bool check()
{
  for (int i = 1; i <= n; i++)
  {
    int start = i;
    for (int j = 1; j <= h; j++)
    {
      if (visited[j][start])
      {
        start++;
      }
      else if (visited[j][start - 1])
        start--;
    }
    if (start != i)
      return false;
  }
  return true;
}
 
void go(int start, int cnt)
{
  if (cnt > 3 || cnt >= ret)
    return;
  if (check())
  {
    ret = cnt;
    return;
  }
 
  for (int i = start; i <= h; i++)
  {
    for (int j = 1; j < n; j++)
    {
      if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1])
        continue;
      visited[i][j] = 1;
      go(i, cnt + 1);
      visited[i][j] = 0;
    }
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m >> h;
  for (int i = 0; i < m; i++)
  {
    cin >> a >> b;
    visited[a][b] = 1;
  }
 
  go(1, 0);
  if (ret == 7)
  {
    cout << -1;
    return 0;
  }
  cout << ret;
}