質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.36%

  • Java

    14359questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • アルゴリズム

    425questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

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

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 307

Stars1024

score 1266

下の図のように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のところを入力形式にして汎用的なものにするつもりですがその点は大丈夫です。)
今思いつくのは

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

checkベストアンサー

+2

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)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/06 11:53 編集

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

    キャンセル

  • 2018/05/06 13:38 編集

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

    キャンセル

+2

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/06 11:56

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

    キャンセル

+2

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)になるはず。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/06 11:56

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

    キャンセル

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/06 11:58

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

    キャンセル

同じタグがついた質問を見る

  • Java

    14359questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • アルゴリズム

    425questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。