백준 14620번 꽃길 ( C++ )

문제

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

 

해설

꽃을 심으려면 상하좌우로 1칸씩 필요하기 때문에 n이 10이라면 1~9칸만 확인하면 된다.

케이스가 10*10 중에 3개를 뽑기 때문에 대략 100만이여서 완탐으로 풀면 간단하게 풀린다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, mp[14][14], visited[14][14];
int ret = 987654321;
 
int flower(int y, int x, int check)
{
  if (check == 0)
  {
    visited[y][x] = 1;
    visited[y - 1][x] = 1;
    visited[y + 1][x] = 1;
    visited[y][x - 1] = 1;
    visited[y][x + 1] = 1;
  }
  else
  {
    visited[y][x] = 0;
    visited[y - 1][x] = 0;
    visited[y + 1][x] = 0;
    visited[y][x - 1] = 0;
    visited[y][x + 1] = 0;
  }
  return mp[y][x] + mp[y - 1][x] + mp[y + 1][x] + mp[y][x - 1] + mp[y][x + 1];
}
 
void go(int y, int x, int cnt, int tmp)
{
  if (cnt == 3)
  {
    ret = min(tmp, ret);
    return;
  }
  for (int j = x; j < n - 1; j++)
  {
    if (!visited[y][j] && !visited[y - 1][j] && !visited[y + 1][j] && !visited[y][j - 1] && !visited[y][j + 1])
    {
      tmp += flower(y, j, 0);
      go(y, j, cnt + 1, tmp);
      tmp -= flower(y, j, 1);
    }
  }
  for (int i = y + 1; i < n - 1; i++)
  {
    for (int j = 1; j < n - 1; j++)
    {
      if (!visited[i][j] && !visited[i - 1][j] && !visited[i + 1][j] && !visited[i][j - 1] && !visited[i][j + 1])
      {
        tmp += flower(i, j, 0);
        go(i, j, cnt + 1, tmp);
        tmp -= flower(i, j, 1);
      }
    }
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> mp[i][j];
    }
  }
 
  go(1, 1, 0, 0);
  cout << ret;
}