[백준 18809] Gaaaaaaaaaarden

=https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
int N, M, G, R;	// 최대 50 * 50맵	// G, R 최대 5개
int board[50 + 2][50 + 2];	// 정보맵
int F[50 + 2][50 + 2];		// 꽃 피우는 맵 
int visited[50 + 2][50 + 2];	// 시간 저장
int ans;

struct _st
{
	int x, y;
};
std::vector<_st> Br;	// 황토색 칸
int br_size;

std::vector<int> Gr;	// Br 벡터의 몇번째 원소 좌표에 해당 배양액 뿌릴 것인지 
std::vector<int> Rd;


struct _qt
{
	int x, y;
	int type;
	int time;
};
std::queue<_qt> Q;


void input()
{
	scanf("%d %d %d %d", &N, &M, &G, &R);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 2) Br.push_back({ i, j });
		}
	}
	br_size = Br.size();
}


int BFS()
{
	// init
	Q = {};
	memset(F, 0, sizeof(F));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = 0x7fffffff;
		}
	}
	int cnt = 0;

	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// 초록색 배양액 뿌리기 
	for (int g : Gr) {
		int gx = Br[g].x;
		int gy = Br[g].y;
		Q.push({ gx, gy, 3, 0 });
		visited[gx][gy] = 0;
		F[gx][gy] = 3;
	}

	// 빨간색 배양액 뿌리기 
	for (int r : Rd) {
		int rx = Br[r].x;
		int ry = Br[r].y;
		Q.push({ rx, ry, 4, 0 });
		visited[rx][ry] = 0;
		F[rx][ry] = 4;
	}


	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();


		// 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 
        // 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다. 
		if (F[data.x][data.y] == -1) continue;	
												

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (board[nx][ny] == 0) continue;
			if (F[nx][ny] == -1) continue;
			if (visited[nx][ny] < data.time + 1) continue;
			if (visited[nx][ny] == data.time + 1 && F[nx][ny] == data.type) continue;
			if (visited[nx][ny] == data.time + 1 && F[nx][ny] != data.type) {
				F[nx][ny] = -1;
				cnt++;
				continue;
			}
			Q.push({ nx, ny, data.type, data.time + 1 });
			visited[nx][ny] = data.time + 1;
			F[nx][ny] = data.type;
		}
		
	}
	return cnt;
}




void DFS(int n, int green, int red)
{
	if (green == G && red == R) {
		int res = BFS();
		if (res > ans) ans = res;
		return;
	}

	if (n == br_size) return;	// 다 골랐다면 리턴


	// 배양액 안뿌린다. 
	DFS(n + 1, green, red);

	// 초록색 배양액 뿌린다.
	Gr.push_back(n);
	DFS(n + 1, green + 1, red);
	Gr.pop_back();

	// 빨간색 배양액 뿌린다. 
	Rd.push_back(n);
	DFS(n + 1, green, red + 1);
	Rd.pop_back();

}



int main()
{
	input();
	DFS(0, 0, 0);	// 몇번째 황토색 칸, 현재까지 뿌린 초록색 배양액 개수, 현재까지 뿌린 빨간색 배양액 개수
	printf("%d\n", ans);
	return 0;
}