[BOJ]2583エリアPythonを求めます

9464 ワード
テキストリンク

画像をクリックして問題に移動します。



質問：面積を求める


ルーラーピッチ1のM×N(M,N≦100)サイズの四角紙があります.この四角紙にK個の矩形を目盛りで描画すると、これらK個の矩形の内部を除いて、残りの部分はいくつかの別々の領域に分割される.
例えば、M=5、N=7の四角紙に<図1>のように3つの矩形を描くと、残りの領域は<図2>のように3つの独立した領域に分割される.

M,N,K,K個の矩形の座標が与えられると,K個の矩形の内部を除いた残りの部分をいくつかの独立した領域に分割し,各分離領域の幅を求めることで出力プログラムを記述する.
import sys
sys.stdin = open('input.txt')
from pprint import pprint
sys.setrecursionlimit(10**6)
M, N, Sqs = map(int, input().split())

board = [[0]* N for _ in range(M)]

dy = [0, 0, -1, 1]
dx = [1, -1, 0, 0]


def dfs(y, x):
    global cnt
    board[y][x] = 1
    cnt += 1

    for i in range(4):
        new_y = y + dy[i]
        new_x = x + dx[i]
        if 0 <= new_y <= M-1 and 0 <= new_x <= N-1:
            if board[new_y][new_x] == 0:
                dfs(new_y, new_x)



for i in range(Sqs):
    lx, ly, rx, ry = map(int, input().split())
    for i in range(lx, rx):
        for j in range(ly, ry):
            board[j][i] = 1

result = []
for i in range(M):
    for j in range(N):
        if board[i][j] == 0:
            cnt = 0
            dfs(i, j)
            result.append(cnt)
print(len(result))
for x in sorted(result):
    print(x, end=' ')
基本的なdfs問題として、0をN*M形式のlistの各パラメータに格納し、与えられた入力座標をリストのグリッド座標に変換し、1に変換すると、基本的なboardが作成されます.
その後,dfs法を用いて,各パーティションが0に遭遇したときにcnt(幅)に1を加え,座標のboard値を1に設定してアクセスの意味とする.
すべての座標に対してdfsを実行すると、各パーティションの幅を求めることができる.
重要なのは、dfs自体に対して、与えられた各座標を私が作成したプレートのメッシュ内の座標に変換するプロセスです.
スクロールナビゲーション
BOJ 2839送糖