質問する

ルーラーピッチ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行目は各領域の幅を昇順に並べ、スペースを隔てて印刷します.

に答える

この問題はBFSで解決できる.MとNが与えられたとき,左下は(0,0),右上は(M,N)であった.筆者はそっくりやって、ミスをして、考えて、やはりその通りに並べた.最終的には異なる形状の領域の個数と幅しか求められないからだ.

の2次元配列に所定の入力値を入れます.
->1に

を入れる

領域数を格納するcount変数と長さを格納するArrayListを作成します.
->ArrayListを使用する理由は、(Collections.sort()

を昇順にソートするためである.

配列の長さでゲート回転を行い、この要素が0の場合count+1を行い、bfsで長さを求めてリストに入れる.

昇順に並べ替えて出力します.

bfs部)
1.座標を保存するPointオブジェクトを作成します.
2.Pointオブジェクトを含むキューを作成します.
3.すでに訪問した場所には二度と行くことができず、booleanの2次元配列を作成します.
4.長さが要求されるためlen変数を宣言します.
5.キューからPointオブジェクトを取り出し、キュー要求まで上、下、左、右方向にチェックします.
6.値が0の場合は1に設定し、その座標をキューに入れます.

ソース

import java.util.*;

class Point {
	private int x;
	private int y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
}

public class Main {
	public static int m, n, k;
	// 상, 하, 좌, 우
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static boolean[][] visited;

	// 0인 부분을 다 1로 바꾸고 바꾼 갯수를 반환
	public static int bfs(int[][] map, int x, int y) {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(x, y));
		int len = 0;
		visited[x][y] = true;

		while (!q.isEmpty()) {
			Point p = q.poll();
			x = p.getX();
			y = p.getY();
			len += 1;

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
					if (visited[nx][ny] == false && map[nx][ny] == 0) {
						map[nx][ny] = 1;
						visited[nx][ny] = true;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}

		return len;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		k = sc.nextInt();

		int[][] map = new int[m][n];
		visited = new boolean[m][n];

		for (int i = 0; i < k; i++) {
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();

			int x2 = sc.nextInt();
			int y2 = sc.nextInt();

			for (int j = y1; j < y2; j++) {
				for (int h = x1; h < x2; h++) {
					map[j][h] = 1;
				}
			}
		}
		// 출력
//		print(map);

		int count = 0;
		ArrayList<Integer> len = new ArrayList<Integer>();

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					count += 1;
					int length = bfs(map, i, j);
					len.add(length);
				}
			}
		}

		// 오름차순 정렬
		Collections.sort(len);

		System.out.println(count);
		for (Integer le : len) {
			System.out.print(le + " ");
		}
	}

	// 배열 출력
	public static void print(int[][] map) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

}