16234번

16234

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n, l, r;
int map[50][50];
int copymap[50][50];
bool visit[50][50] = { false, };
vector<pair<int, int> > points;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void dfs(int x, int y) {
	visit[x][y] = true;
	points.push_back(make_pair(x, y));

	for (int i = 0; i < 4; i++) {
		int tmpx = x + dx[i];
		int tmpy = y + dy[i];
		if (tmpx < 0 || tmpx >= n || tmpy < 0 || tmpy >= n) {
			continue;
		}

		int diff = abs(map[x][y] - map[tmpx][tmpy]);

		if (!visit[tmpx][tmpy] && diff >= l && diff <= r) {
			dfs(tmpx, tmpy);
		}
	}
}

void initVisit() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = false;
		}
	}
}

void copy() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = copymap[i][j];
		}
	}
}

void calcPeople() {
	int sum = 0;
	for (int i = 0; i < points.size(); i++) {
		int x = points[i].first;
		int y = points[i].second;
		sum += map[x][y];
	}
	int newCnt = floor(sum / points.size());

	for (int i = 0; i < points.size(); i++) {
		int x = points[i].first;
		int y = points[i].second;
		copymap[x][y] = newCnt;
	}
}

bool checkSame() {
	bool isSame = true;
	for (int k = 0; k < n; k++) {
		for (int z = 0; z < n; z++) {
			if (copymap[k][z] != map[k][z]) {
				isSame = false;
				break;
			}
			if (!isSame) break;
		}
	}
	if (isSame) {
		return true;
	}
	copy();
	return false;
}

int main() {
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			copymap[i][j] = map[i][j];
		}
	}

	int answer = 0;
	while (true) {
		initVisit();
		bool result = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visit[i][j]) {
					dfs(i, j);
					calcPeople();
					points.clear();
				}
			}
		}

		if (checkSame()) {
			break;
		}

		answer++;
	}
	cout << answer;
}