白俊2667号です.
https://www.acmicpc.net/problem/2667

質問する

図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それはつながった家の集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.<【図2】<図1>を単一番号で示す図である.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.

入力

1行目は地図サイズN(正方形、横方向と縦方向のサイズが同じ、5≦N≦25)を入力し、次の行は各N個の資料(0または1)を入力する.

しゅつりょく

最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べ、各行に1つ出力します.

入力例

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

サンプル出力

3
7
8
9

考える

久しぶりのDFS/BFS問題…果たして解けるのか?考えましたが、あまりにも簡単に成功したので、気持ちがいいです.
他に特別な点がなく、DFSの概念しか知らないと、解決しやすい問題です.

アクション

	static int arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};

	static int count = 0, number = 0;
	static int nowX, nowY, N;

DFSは常に再帰的な方法を使用するため,静的および静的変数がしばしば使用される.
だから私は多くの変数を作った.dirXおよびdirYは、単点番号の場合、対角線を除いて上下左右の単点に番号を付与することを示す.dirXは上下左右で左右を判断し、dirYは、上下の範囲を判断するために上下左右に並べられている.
なぜこの配列が必要なのか考えることができます.dirXを例にとると、左へ行くには基点−1、右へ行くには+1が必要であるため、その配列が必要である.nowXおよびnowYは、範囲座標を計算する変数である.

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		visit = new boolean[N][N];

		for(int i=0; i<N; i++) {
			String str = br.readLine();

			for(int j=0; j<N; j++) {				
				arr[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}

この部分はinputを配列した部分です.

		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {

				if(visit[i][j] == false && arr[i][j] == 1) {
					count = 0;
					number++;
					DFS(i, j);	
					list.add(count);
				}

			}
		}

DFS()は接続の1に沿ってまっすぐしか歩かないので,すべての面に0があると歩き続けることができないと判断して方法を終了する.したがって、配列全体をブラウズする際に、アクセスがなく、arrの中で1つの位置に遭遇した場合、DFS()メソッドを再度実行すると、arr全体をブラウズすることができる.listは各団地の家屋の数字を格納するために建てられた.

	static void DFS(int x, int y) {
		visit[x][y] = true;
		arr[x][y] = number;
		count ++;

		for(int i=0; i<4; i++) {
			nowX = dirX[i] + x;
			nowY = dirY[i] + y;

			if(Range_check() && visit[nowX][nowY] == false && arr[nowX][nowY] == 1) {
				visit[nowX][nowY] = true;
				arr[nowX][nowY] = number;

				DFS(nowX, nowY);
			}
		}		

	} // End of DFS

DFS()プロセスは、上述の接続であるarrが1でアクセスされていない場合は、実行
[x][y]=trueにアクセスして実行の瞬間アクセスを表示し、arr[x][y]=numberを行うだけです.加入する.

			nowX = dirX[i] + x;
			nowY = dirY[i] + y;

ここでは、nowXおよびnowYを格納する適切な範囲の値を算出する.
後続のRange check()メソッドが範囲条件でtrueの場合のみ
アクセスの有無をtrueに変換し、番号を1つだけ与えます.
この過程を繰り返すことで問題を解決することができる.

コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	static int arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};

	static int count = 0, number = 0;
	static int nowX, nowY, N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		List<Integer> list = new ArrayList<>();

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		visit = new boolean[N][N];

		for(int i=0; i<N; i++) {
			String str = br.readLine();

			for(int j=0; j<N; j++) {				
				arr[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {

				if(visit[i][j] == false && arr[i][j] == 1) {
					count = 0;
					number++;
					DFS(i, j);	
					list.add(count);
				}

			}
		}

		Collections.sort(list);
		bw.append(number + "\n");
		for(int num : list) {
			bw.append(num + "\n");
		}

		bw.flush();
		bw.close();		
	} // End of main

	static void DFS(int x, int y) {
		visit[x][y] = true;
		arr[x][y] = number;
		count ++;

		for(int i=0; i<4; i++) {
			nowX = dirX[i] + x;
			nowY = dirY[i] + y;

			if(Range_check() && visit[nowX][nowY] == false && arr[nowX][nowY] == 1) {
				visit[nowX][nowY] = true;
				arr[nowX][nowY] = number;

				DFS(nowX, nowY);
			}
		}		

	} // End of DFS

	static boolean Range_check() {
		return (nowX >= 0 && nowX < N && nowY >= 0 && nowY < N);
	} // End of Range_check
} // End of class