나무박멸

Simulation

평균 : 180'

---

sol : 75' 38''

• 수행시간 : 15ms
• 메모리 : 0MB

Learnings

• '제초제 지속 연도' 설정할 때, 감소 시점을 루틴 속에 넣으면 잠재적 위험요소가 될 수 있으니, 차라리 다시 번식 가능한 연도 자체를 넣어주는 것이 정도이다.

#include <iostream>
#include <utility>
#include <vector>

#define MAX_N 20
#define WALL -1
#define EMPTY 0
#define DIRECTIONS 4

using namespace std;

int n, m, k, c;
int killed;
pair<int, int> ds[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

int grid[MAX_N][MAX_N];
int herbiMap[MAX_N][MAX_N];

////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////

void Debug(int g[MAX_N][MAX_N]) {
	cout << endl <<  "DEBUG" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG END" << endl << endl;
}

bool Inbound(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void DupGrid(int from[MAX_N][MAX_N], int to[MAX_N][MAX_N]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void grow() {
	int temp[MAX_N][MAX_N];
	DupGrid(grid, temp);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] > 0) {
				int cnt = 0;
				for (int d = 0; d < DIRECTIONS; d++) {
					int ni = i + ds[d].first, nj = j + ds[d].second;

					if (Inbound(ni, nj) && grid[ni][nj] > 0) {
						cnt++;
					}
				}
				temp[i][j] += cnt;
			}
		}
	}
	DupGrid(temp, grid);
}

void breed() {
	int temp[MAX_N][MAX_N];
	DupGrid(grid, temp);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] > 0) {
				vector<pair<int, int>> posIndices;
				for (int d = 0; d < DIRECTIONS; d++) {
					int ni = i + ds[d].first, nj = j + ds[d].second;

					if (Inbound(ni, nj) && grid[ni][nj] == EMPTY && herbiMap[ni][nj] == EMPTY) {
						posIndices.push_back({ ni, nj });
					}
				}

				for (int breedNum = 0; breedNum < posIndices.size(); breedNum++) {
					int bi = posIndices[breedNum].first, bj = posIndices[breedNum].second;
					temp[bi][bj] += (grid[i][j] / posIndices.size());
				}
			}
		}
	}
	DupGrid(temp, grid);
}

void FindMaxSpot(pair<int, int>& spot) {
	pair<int, int> cross[4] = { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };

	int maxKill = 0;
	spot = { -1, -1 };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] > 0) {
				int curKill = grid[i][j];
				for (int d = 0; d < DIRECTIONS; d++) {
					for (int range = 1; range <= k; range++) {
						int ni = i + cross[d].first * range, nj = j + cross[d].second * range;

						if (!Inbound(ni, nj) || grid[ni][nj] == WALL || grid[ni][nj] == EMPTY) break;
						else if (Inbound(ni, nj) && grid[ni][nj] > 0) {
							curKill += grid[ni][nj];
						}
					}
				}

				if (curKill > maxKill) {
					maxKill = curKill;
					spot = { i, j };
				}

				if (curKill == maxKill) {
					if (spot.first > i) {
						spot = { i, j };
					}
					else if (spot.first == i) {
						if (spot.second > j) {
							spot = { i, j };
						}
					}
				}
			}
		}
	}
}

void DoHerbicide(pair<int, int> spot) {
	pair<int, int> cross[4] = { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
	
	killed += grid[spot.first][spot.second];
	grid[spot.first][spot.second] = 0;
	herbiMap[spot.first][spot.second] = c;
	

	for (int d = 0; d < DIRECTIONS; d++) {
		for (int range = 1; range <= k; range++) {
			int ni = spot.first + cross[d].first * range, nj = spot.second + cross[d].second * range;

			if (!Inbound(ni, nj)) break;
			else if (grid[ni][nj] == WALL || grid[ni][nj] == EMPTY) {
				herbiMap[ni][nj] = c;
				break;
			}
			else if (grid[ni][nj] > 0) {
				killed += grid[ni][nj];
				grid[ni][nj] = EMPTY;
				herbiMap[ni][nj] = c;
			}
		}
	}
}

void DecHerbicide() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (herbiMap[i][j] > 0) herbiMap[i][j]--;
		}
	}
}

void Herbicide() {
	pair<int, int> spot;

	FindMaxSpot(spot);

	DecHerbicide();

	//cout << "spot : " << spot.first << " " << spot.second << endl;

	if (spot.first == -1 && spot.second == -1) return;

	DoHerbicide(spot);
}

int main() {
	cin >> n >> m >> k >> c;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
		}
	}

	for (int year = 1; year <= m; year++) {
		grow();
		//cout << "after grow";
		//Debug(grid);

		breed();
		//cout << "after breed";
		//Debug(grid);

		Herbicide();
		//cout << "after herbicide";
		//Debug(grid);
	}
	
	cout << killed;

	return 0;
}