白駿16234号人口移転

質問する

コード#コード#

cpp

#include <vector>
#include <iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;

int abs(int n) {
	if (n >= 0) return n;
	else return -n;
}

int main() {
	int answer = 0;
	int n, l, r;
	cin >> n >> l >> r;

	vector<vector<int>> map1(n, vector<int>(n, 0));
	

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

	
	int count = 1;
	int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

	while (1) {
		vector<vector<int>> map2(n, vector<int>(n, 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map2[i][j] != 0) continue;
				queue<pair<int, int>> q;
				q.push({ i,j });
				
				while (!q.empty()) {
					
					int y = q.front().first;
					int x = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++) {
						int new_y = y + dir[k][0];
						int new_x = x + dir[k][1];
						if (0 > new_y || new_y >= n || 0 > new_x || new_x >= n) continue;
						if (map2[new_y][new_x] != 0 ||
							l > abs(map1[y][x] - map1[new_y][new_x]) ||
							r < abs(map1[y][x] - map1[new_y][new_x])) continue;
						
						map2[y][x] = count;
						map2[new_y][new_x] = count;
						q.push({ new_y,new_x });
					}
				}
				count++;
			}				
		}
		// ----------인구이동이 있는지 검사
		bool result = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				if (map2[i][j] != 0) {
					result = false;
				}
			}	
		}
		if (result) break; //만약 없다면 while문 종료
		
		answer++; 
		map<int, pair<int, int>> hash;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				hash[map2[i][j]].first += map1[i][j];
				hash[map2[i][j]].second++;
			}
		}
		vector<pair<int, int>> list;
		for (auto i : hash) {
			if (i.first == 0) continue;
			list.push_back({ i.first,i.second.first / i.second.second });
		}
		for (int i = 0; i < list.size(); i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (map2[j][k] == list[i].first)
						map1[j][k] = list[i].second;
				}
			}
		}

	}

	cout << answer;
}

python

from collections import deque


def bfs(num, i, j):
    q = deque()
    q.append((i, j))

    cnt = 1
    sum_v = board[i][j]

    while q:
        y, x = q.popleft()

        for dy, dx in d:
            newy = y+dy
            newx = x+dx
            if newy >= n or newy < 0 or newx >= n or newx < 0 or temp[newy][newx] != -1:
                continue

            if l <= abs(board[newy][newx]-board[y][x]) <= r:
                temp[newy][newx] = num
                sum_v += board[newy][newx]
                cnt += 1
                q.append((newy, newx))
    return cnt, sum_v


n, l, r = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(n)]

d = [[0, 1], [0, -1], [1, 0], [-1, 0]]


answer = 0

isTrans = True

while isTrans:
    isTrans = False
    lis = []
    num = 0
    temp = [[-1]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if temp[i][j] != -1:
                continue

            temp[i][j] = num
            cnt, sum_v = bfs(num, i, j)
            lis.append(sum_v//cnt)

            num += 1

            if cnt != 1:
                isTrans = True

    for i in range(n):
        for j in range(n):
            board[i][j] = lis[temp[i][j]]

    answer += 1

print(answer-1)

に答える

2 20 50
20 100
50 140