[伯俊]贴BOJ 2667小区号JAVA

22396 ワード
アルゴリズム#アルゴリズム# テキストリンク
番号BOJ 2667のみ

質問する


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

入力


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

しゅつりょく


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

サンプルI/O



ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int n, cnt;
    private static int[][] map;
    private static boolean[][] visit;
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visit = new boolean[n][n];
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                map[i][j] = line[j] - '0';
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && map[i][j] == 1) {
                    cnt = 1;
                    bfs(i, j);
                    ans.add(cnt);
                }
            }
        }

        int size = ans.size();
        Collections.sort(ans);
        System.out.println(size);
        for (int value : ans) {
            System.out.println(value);
        }
    }

    private static void bfs(int x, int y) {
        Queue<Pos> q = new LinkedList<>();
        visit[x][y] = true;
        q.add(new Pos(x, y));

        while (!q.isEmpty()) {
            int curX = q.peek().x;
            int curY = q.peek().y;

            q.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];

                if (!isScope(nextX, nextY)) continue;

                if (!visit[nextX][nextY] && map[nextX][nextY] != 0) {
                    q.add(new Pos(nextX, nextY));
                    visit[nextX][nextY] = true;
                    cnt++;
                }
            }
        }
    }

    /*private static void dfs(int x, int y) {
        visit[x][y] = true;

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

            if (!isScope(nx, ny)) continue;

            if (!visit[nx][ny] && map[nx][ny] != 0) {
                cnt++;
                visit[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }*/

    private static boolean isScope(int x, int y) {
        return (x >= 0) && (x < n) && (y >= 0) && (y < n);
    }

    private static class Pos {
        int x;
        int y;

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

Comment


これは
  • の二次元座標を用いた典型的なdfs,bfs問題である.dxおよびdyを使用して座標を移動し、条件を満たすかどうかの問題を特定します.
  • 座標は、通常、2 Dアレイで4つの方向を使用します.
  • i=0の場合、(-1,0)を指す座標を↑方向とすると、スペースが表示されます.
  • i=1の場合、(0,1)は座標→方向、1つのセルの右側を表します.
  • i=2の場合、(1,0)を座標として、↓方向であり、1段下を表す.
  • i=3の場合、(0,-1)を指す点を座標とすると←方向、左一格を表します.
  • によって初期化された2次元配列の範囲を超えないようにするために、isScope法が使用される.
  • ビットのような問題のタイプはたくさんあります.多く解いて熟すと、答えが見つかりやすい.
    • 特にdfs:再帰/bfs:Queueを利用する点である.
    トリガー:削除時にトリガーして情報を記録する
    Debian 10はstretchバージョン163ソースに変更されました