質問する

https://www.acmicpc.net/problem/16234
N×Nサイズの地があり、地は1×格子に分ける.どの土地にも一つの国があり、r行c列の国にはA[r][c]名が住んでいる.隣国の間に境界線がある.すべての国×1サイズなので、すべての境界は正方形です.
今日から人口移転の日です.
人口移転は1日以内に以下の方法で行われ、以下の方法で人口移転が行われなくなるまで行われる.

国境線を共有する両国の人口差がL名以上、R名以下であれば、両国が共有する国境線は今日開かれる.

位の条件に従ってすべての境界線を開くと、人口の流れが開始される.

国境線が開いていて、隣の1つの格子でしか移動できないなら、今日の1日でこの国は連合と呼ばれています.

連合体を構成する各間の人口数は(連合体の人口数)/(連合体の個数)である.便利な小数点を捨てる.

連盟を解散し、すべての国境線を閉鎖した.

国ごとの人口数が与えられると、人口の流れが数日以内に発生する状況を知るプログラムを作成してください.

入力

1行目はN,L,Rである.(1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
2列目から、国ごとの人口数がN行に割り当てられます.r行c列に与えられる整数は、A[r][c]の値である.(0 ≤ A[r][c] ≤ 100)
人口移転が発生した日数が2000回未満の入力のみを与えます.

しゅつりょく

人口の流れは数日発生し,1行目に並んだ.

アイデア

👎 一つの数字で連合できる国を表現した.

例入力3~

2 20 50
50 30
30 40

入力があれば.
chk=[1,1],[1,0]のように現れ,0の領域は連合できない国である.

例

4 10 50
10 100 50 50
50 50 50 50
50 50 50 50
50 50 100 50

chk = [[1, 2, 2, 0], [1, 2, 0, 0], [0, 0, 3, 0], [0, 3, 3, 3]]
このようにchkを作成し、同じ数字の間に加算し、arrを変更します.

マイコードpypy 3

::pythonを使用する場合は、pyty 3が通過するまでタイムアウトする必要があります。

まだちょっと乱れたハーモニーがあります...
もう少し考えを整理して、問題を解決しなければなりません.

from collections import deque

n, l, r = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]  #반시계 방향
ans = 0
while True:
    result = {}     #{1:[120, [[0,1],[0,3],[1,2]]}이런 식으로 들어감 => 각 칸 인구의 합, 칸 인덱스
    chk = [[0] * n for x in range(n)]
    cnt = 1
    for i in range(n):
        for j in range(n):
            if chk[i][j] == 0:
                queue = deque()
                queue.append([i, j])
                s = 0   #연합 국가의 인구 수의 합
                tmp = []    #연합 국가의 인덱스 담을 배열
                while queue:
                    x, y = queue.popleft()
                    chk[x][y] = cnt
                    s += arr[x][y]
                    tmp.append([x,y])
                    for k in range(4):
                        nx = x + direction[k][0]
                        ny = y + direction[k][1]
                        if 0 <= nx < n and 0 <= ny < n:
                            if l <= abs(arr[nx][ny] - arr[x][y]) <= r and chk[nx][ny] == 0:
                                chk[nx][ny] = cnt
                                queue.append([nx, ny])
                            #다른 국가와 연합할 수 없으면 0으로 저장
                            if k == 3 and x == i and y == j and not queue:
                                chk[x][y] = 0
                                cnt -= 1
                            else:
                                chk[x][y] = cnt
                        else:
                            if k == 3 and x == i and y == j and not queue:
                                chk[x][y] = 0
                                cnt -= 1
                cnt += 1
                #result에 연합 인구 수의 총 합과 인덱스 저장
                if chk[i][j] != 0:
                    result[cnt-1] = [s]
                    result[cnt-1].append(tmp)
    if len(result) == 0:    #더이상 연합할 수 없으면 종료
        print(ans)
        break
    #연합한 국가들의 인구수를 변경함
    for i in range(1, len(result)+1):
        p = int(result[i][0]/len(result[i][1]))
        for j in range(len(result[i][1])):
            arr[result[i][1][j][0]][result[i][1][j][1]] = p
    ans += 1

[#Clone]コードpy 3

::pythonではなく、pypy 3でなければ...を通過できません。

from collections import deque

n, l, r = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]  #반시계 방향
ans = 0


def bfs(start):
    global move
    queue = deque()
    queue.append(start)
    visited[start[0]][start[1]] = True
    s = arr[start[0]][start[1]]
    tmp = [start]
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + direction[k][0]
            ny = y + direction[k][1]
            if 0 <= nx < n and 0 <= ny < n:
                if l <= abs(arr[nx][ny] - arr[x][y]) <= r and not visited[nx][ny]:
                    queue.append([nx, ny])
                    visited[nx][ny] = True
                    tmp.append([nx, ny])
                    s += arr[nx][ny]
    if len(tmp) > 1:
        move = True
        for t in range(len(tmp)):
            arr[tmp[t][0]][tmp[t][1]] = int(s / len(tmp))


while True:
    visited = [[False]*n for x in range(n)]
    move = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs([i, j])
    if move:
        ans += 1
    else:
        print(ans)
        break

クローン関数のソース