塊の面積の最大値を求めたいです。

Question

下の図のように4*4のマスに黒い■がいくつかあります。

例えば黒い■はいくつあるか数えるのだったら次のコードで求めることができます

    int [][]data = {{1,0,0,1},{1,0,0,0},{1,1,0,0},{0,1,0,1}};
    int count = 0;
    for(int i = 0; i < 4; i++){
    	for(int j = 0; j < 4; j++){
    		if(data[i][j] == 1){
    			count++;
    		}
    	}
    }
    System.out.println(count);

これはわかるのですが、問題は黒い■の塊の最大値です。上で使用した図だとMax = 5　と
なりますが、これを導く方法がいまいちわかりません。
(最終的には4*4のところを入力形式にして汎用的なものにするつもりですがその点は大丈夫です。)
今思いつくのは

つながっているところの面積をそれぞれ算出し、それらの最大値を求める。

どうやって、つながっているところの面積を出すのかがわかりません。
(ほかの方法があるのかもしれません。)
どなたかわかる方、ご教授お願いします。

Answer 1

mkgreiさんやswordoneさんがが示しているようにFlood fillを使うのだと思われます。

• 一つのマスから繋がっているマスを再帰で探しに行く。
• マスが見つかれば+1するか、再帰的にマスの数を足していくかの二通り。mkgreiさんの回答のリンク先は前者(たぶん)、後述のサンプルでは後者を採用している。
• ループしている場合があるので既に見たかの確認が必要。
• 左や上に戻る場合もあるので全方向について確認が必要。
• 分離された別の塊の存在もあるので、最終的には全マスについてチェック済みかの確認が必要。
• 全体の大きさの半分以上なら他のグループは探索しなくて良い。計算量としては半分になるだけなので、最悪時間も変わらないから、探索打ち切りしなくてもオーダーとしてはあまり影響しない(たぶん)。
• 計算量はO(n)かな？。nはマスの数(幅x高さ)。唐松模様だと4回見られるマスが増えるけど、余り影響しないはず。

実装サンプル。(Java10以上必須、Java9以下ではコンパイル不可)

import java.util.stream.IntStream;
import java.util.Scanner;

public class KatamariFloodFill {
    public static void main(String ... args) {
        final var sc = new Scanner(System.in);
        final var width = sc.nextInt();
        final var height = sc.nextInt();
        final var list = new boolean[height + 2][width + 2];
        final var checked = new boolean[height + 2][width + 2];

        IntStream.rangeClosed(1, height).forEachOrdered(y -> {
            IntStream.rangeClosed(1, width).forEachOrdered(x -> {
                list[y][x] = sc.nextInt() == 1;
            });
        });

        final var result = IntStream.rangeClosed(1, height).map(y ->
                IntStream.rangeClosed(1, width).map(x ->
                        countConnectMasu(list, checked, x, y)).max().orElse(0)
        ).max().orElse(0);

        System.out.println(result);
    }

    static int countConnectMasu(boolean[][] list, boolean[][] checked,
                                int x, int y) {
        if (!list[y][x] || checked[y][x]) return 0;
        checked[y][x] = true;
        return 1 +                                              // self
               countConnectMasu(list, checked, x - 1, y) +      // left
               countConnectMasu(list, checked, x, y - 1) +      // up
               countConnectMasu(list, checked, x + 1, y) +      // right
               countConnectMasu(list, checked, x, y + 1);       // down
    }
}

なお、入力ファイルはこんな形を想定しています。

4 4
1 0 0 1
1 0 0 0
1 1 0 0
0 1 0 1

---

別の方法としては、マス毎にグループ番号を付けていくというのがあるのですが、グループが結合するときの処理が非常に面倒そうなので、あまりよくないかも。こちらも計算量はO(n)になるはず。

Comments

[退会済みユーザー]

回答ありがとうございます。
「•全体の大きさの半分以上なら他のグループは探索しなくて良い。」という考え方が重要だと
感じました。

Answer 2

単純に考えるなら、
■があったら、その周辺の■を探し、その■の周辺の■を探し…とやっていく方法が挙げられます。
また、そのマスを一度見たかをチェックするbooleanの配列も必要でしょうか。
再帰で定義すると比較的楽かと思います。

Comments

[退会済みユーザー]

回答ありがとうございます。「再帰」で解く方法が勉強になりました。

Answer 3

https://tekmarathon.com/2012/10/04/find-length-of-connected-cells-of-1ssector-in-an-matrix-of-0s-and-1s/

こちらのアルゴリズムを少しいじればほしい解が得られます。

---

javaではなく、Pythonですが。

a = [[1,0,0,1,1,0],
     [1,0,0,0,1,1],
     [1,1,0,0,1,0],
     [0,1,0,1,1,1]]
from pprint import pprint
pprint(a)

def find(b, c, i, j, d=0):
    if (i>=0 and i<len(b[0])
        and j>=0 and j<len(b)
        and (c[j][i] is False) and b[j][i]==1):
        d += 1
        c[j][i] = True
        d = find(b, c, i-1, j, d=d)
        d = find(b, c, i+1, j, d=d)
        d = find(b, c, i, j-1, d=d)
        d = find(b, c, i, j+1, d=d)
    return d

def gen_bool(b):
    c = [[False for _ in range(len(b[0]))] for _ in range(len(b))]
    return c

ans = 0
c = gen_bool(a)
for j in range(len(a)):
    for i in range(len(a[0])):
        if a[j][i]==1 and (c[j][i] is False):
            d = find(a, c, i, j)
            if d>ans:
                ans = d
print(ans)

Comments

[退会済みユーザー]

回答ありがとうございました。pythonは最近勉強したばかりですが頑張って読んで
Javaで書こうと思います。

[退会済みユーザー]

無事、Javaに移植することができました。ありがとうございました。

Answer 4

"2d iland java find"
で google 検索すると、 (!, 1) の値の 2D マトリックスから １ の塊の数を求めるという問題の java での対処例をたくさん見つけることができます。

これを変更して、見つけた島のそれぞれの面積をもとめるようにできると思います。

Comments

[退会済みユーザー]

回答ありがとうございます。"2d iland java find"で検索したら関連した問題がいくつか出たので
それを参考にしたいと思います。