꽃길

이전에 했던부분 재 분석임.

이전에는 flowerVisitied랑 visitied두개를 놔두고 탐색을 해서 계속 틀렸었다. 그래서 질문글 올리니까

지금 딱 이런경우 하늘색 꽃이 판별이 안된다 내가 이전에 했던 코드처럼 하면

이전코드 로직은 그럴싸한데 예외사항을 체크를 못했었음.

그리고 Go함수안에서 그냥 이중for문 돌려서 모든 부분을 탐색할 수 있도록 한부분이 컷다.

cpp

#include <iostream>
#include <cstring>
using namespace std;

int n, arr[12][12], visited[12][12], dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
int MinValue = 1e9;

bool Cango(int y, int x)
{
	if (y < 0 || x < 0 || y >= n || x >= n || visited[y][x]) return false;
	return true;
}

bool Check(int y, int x)
{
	if (!Cango(y, x)) return false;
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!Cango(ny, nx)) return false;
	}
	return true;
}

int CalVaule(int Arr[12][12])
{
	int ret = 0;
	for (int y = 0; y < n; ++y)
	{
		for (int x = 0; x < n; ++x)
		{
			if (Arr[y][x] == 1) ret += arr[y][x];
		}
	}
	return ret;
}

void Seed(int y, int x)
{
	visited[y][x] = 1;
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		visited[ny][nx] = 1;
	}
}

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

void Go(int cnt)
{
	if (cnt == 3)
	{
		MinValue = min(MinValue, CalVaule(visited));
		return;
	}
	
	for (int y = 0; y < n; ++y)
	{
		for (int x = 0; x < n; ++x)
		{
			if (Check(y, x))
			{
				Seed(y, x);
				Go(cnt + 1);
				DeSeed(y, x);
			}
		}
	}
}

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 >> arr[i][j];

	Go(0);
	cout << MinValue << endl;

	return 0;
}