[伯俊]2583面積を求める

面積を求める

質問する

ルーラーピッチ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個の矩形の内部を除いた残りの部分をいくつかの独立した領域に分割し,各分離領域の幅を求めることで出力プログラムを記述する.

入力

第1行MとN,Kは、スペースを隔てて順次与えられる.M,N,Kはいずれも100以下の自然数である.2行目からK行目まで、矩形左下角頂点のx、y座標値、右上角頂点のx、y座標値は、行ごとにスペースを隔てて順次与えられる.四角い紙の左下の頂点の座標は(0,0)、右上の頂点の座標は(N,M)です.入力したK個の長方形は、丸み紙全体を埋めません.

しゅつりょく

最初の行の区切り領域の数を出力します.2行目は各領域の幅を昇順に並べ、スペースを隔てて印刷します.

チップ...?

(0,0)(7,5)を(0,0)(5,7)に変換し,入力した座標値をx座標,y座標と逆に考えれば簡単に解くことができる.

コミットコード

import sys
from collections import deque
input = sys.stdin.readline

m, n, k = map(int, input().split())
table = [[0] * n for _ in range(m)]
visited = [[-1] * n for _ in range(m)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for _ in range(k):
    ly, lx, ry, rx = map(int, input().split())
    for i in range(lx, rx):
        for j in range(ly, ry):
            table[i][j] = 1
def bfs(_x, _y, c):
    q = deque()
    q.append([_x, _y])
    visited[_x][_y] = c
    while q:
        xx, yy = q.popleft()
     
        for i in range(4):
            x = xx + dx[i]
            y = yy + dy[i]
          
            if x < 0 or y < 0 or x >= m or y >= n: continue
            if visited[x][y] != -1: continue
            if table[x][y] != 0: continue
            visited[x][y] = c
            q.append([x, y]) 

cnt = 0
for i in range(m):
    for j in range(n):
        if table[i][j] == 0 and visited[i][j] == -1:
            bfs(i, j, cnt)
            cnt += 1

answer = []
for i in range(cnt):
    a = 0
    for k in range(m):
        for j in range(n):
            if visited[k][j] == i:
                a += 1
    answer.append(a)
answer.sort()
print(cnt)
for i in answer:
    print(i, end=' ')