[白俊-2583]獲得領域

10843 ワード
BFS/DFS テキストリンク
質問する
ルーラーピッチ1のM×N(M,N≦100)サイズの四角紙があります.この四角紙にK個の矩形を目盛りで描画すると、これらK個の矩形の内部を除いて、残りの部分はいくつかの別々の領域に分割される.
例えば、M=5、N=7の四角紙に<図1>のように3つの矩形を描くと、残りの領域は<図2>のように3つの独立した領域に分割される.
「図2」に示すように、3つの領域の幅はそれぞれ1、7、13である.
M,N,K,K個の矩形の座標が与えられると,K個の矩形の内部を除いた残りの部分をいくつかの独立した領域に分割し,各分離領域の幅を求めることで出力プログラムを記述する.
リンク
に答える
この問題もbfsで解決した.
私はただbfsですべての問題を解決したいだけです.
from collections import deque

m, n, k = map(int, input().split())

# 일단 모눈 종이 만들기
graph = [[0]*n for _ in range(m)]

# 모눈 종이에 직사각형 그리기
# 배열에서 [x][y] 랑 좌표에서  [x][y]랑 반대라서 뒤집어서 입력받음
for _ in range(k) :
    j1, i1, j2, i2 = map(int, input().split())
    for i in range(i1, i2) :
        for j in range(j1, j2) :
            if graph[i][j] == 0 :
                graph[i][j] = 1

# 상, 하, 좌, 우
da = [-1, 1, 0, 0]
db = [0,0,-1,1]

def solution(a, b) :
    area = 1 # 넓이
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 1
    while queue :
        a, b = queue.popleft()
        for i in range(4) :
            na = a + da[i]
            nb = b + db[i]
            if na <= -1 or na >= m or nb <= -1 or nb >= n :
                continue
            if graph[na][nb] == 0 :
                graph[na][nb] = 1
                queue.append((na, nb))
                area += 1
    answer.append(area)

count = 0 # 분리된 영역
answer = []
for a in range(m) :
    for b in range(n) :
        if graph[a][b] == 0 :
            solution(a, b)
            count += 1

answer.sort()
#리스트 안의 숫자를 문자로 변경
answer = list(map(str, answer))
print(count)
print(' '.join(answer))
  • 四角紙
    • を作成する.
  • 四角紙に長方形
    • を描画する.
  • すべてのノードにわたって独立した領域幅と数
    • を求める.
    DFSとBFSの問題を徐々に解決できてよかったです.
    一緒にコテレ襲撃に行きましょう.
    BaseRecyclerViewAdapterHelperマルチレイアウト実装
    [Java]白準11724号/接続要素数