0と1が入力される多次元配列の1を囲う棒の数え方

Question

スクールの課題です。

1、多次元配列の広さを入力
例：4　4
2、指定された広さ分の情報の入力
例：１
4 4
0010
1110
0010
0010

例：2
3 5
00010
11001
01100

3、1を囲うのに必要な棒が何本必要か計算して出力
例：1は14本
例：2は18本

現在の考え方
1を囲うのに4本必要　－　重なっている分（1つの場所で2本）　＝　必要な本数
例で考えると
（4×6）－　（5×2）＝　24　－　10　＝　14
（4×6）－　（3×2）＝　24　－　6　＝　18
で求められるとわかりました。

しかし、途中でどうやってプログラミングをすればいいのかわからなくなってしまいました。
ループの中で要素数が一致するのを数えようと思ったのですが…timelimit exceededになりました。

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int heigt = sc.nextInt();   //高さを取得
        int width = sc.nextInt();   //幅を取得h);
        
        //情報を1文字ずつ配列に格納していく
        String[][] flower = new String[heigt][width];
        int count = 0;  //#の数を数える
        for (int i = 0; i < heigt; i++ ){
            String str = sc.next();
            for (int j = 0; j < width; j++ ){
                char[] arrayC = str.toCharArray();     //1文字ずつに変換
                Character tmp = arrayC[j];
                flower[i][j] = tmp.toString();
                if("#".equals(flower[i][j])){
                    //#の数を数える
                    count++;
                }
            }
        } 
        System.out.println(count);
        int count2 = 0; //#の縦の要素数が一緒がいくつあるか
        int count3 = 0; //#が連続で続いているか
        int[][] flg = new int[heigt][width]; //#があるか確認したら1にする
        int idx = 0;
        for (int i = 0; i < heigt; ){
            for (int j = 0; j < width; j++ ){
                if(flg[i][j] == 0 && "#".equals(flower[i][j])){
                    //#の位置の要素数を保存
                    idx = j;
                    flg[i][j] = 1;
                }else{
                    //#がなければflgをあげる（確認済）
                    flg[i][j] = 1;
                }
            }
            if(i > 0){
                for (int k = 0; k < width; k++ ){
                    if("#".equals(flower[i][k]) && idx == k){
                        //#　かつ　前のと同じ位置の場合カウントする
                        count2++;
                    }
                }
            }
        }
        System.out.println(count2);
    }
}
コード

間違っている点や
他の考え方など、ご教授いただければと思います。
よろしくお願いいたします。

Comments

[Zuishin]

なぜ 14 本と 18 本になるのかどうしてもわかりません。これは正しい答えですか？
棒を 2 で表すと、次のようになるのではないですか？
00020
02212
21112
02212
00212
00020

[kinako_make]

図のようであっていますが、角の部分が2本必要なので「2」の数と異なります。
111
021
上記のように「2」で表すと1つですが、実際の棒は「2」の上と右側に必要なので2つとして数えます。
わかりにくくて、すみませんがこの説明で理解できますでしょうか。

[Daregada]

(説明不足なんですが)おそらく、縦と横を囲む棒を別に考えるのではないかと。
_|1
1 1
みたいに。って書いている間に補足があったわ。

問題2は、4行目が記述漏れの可能性がある。

[Zuishin]

なるほど。「棒」の意味がわかりました。

[Zuishin]

アルゴリズムとしては、まず 1 の数を数えてそれを 4 倍し、一つ一つの 1 を見て隣接する 1 の数を引けばいいと思います。多分質問に書いてあるのと同じですね。

この場合、

0010
1110
0010
0010

これをまず

000000
000100
011100
000100
000100
000000

このように変換すると、1 の隣に 1 か 0 があることが保証されるので、アルゴリズムが単純になると思います。その上で隣接した 1 の数を数えて次のように変換します。

000000
000100
012300
000200
000100
000000

そうすると引く数は 1 + 1 + 2 + 3 + 2 + 1 = 10 になるので、6 * 4 - 10 = 14 が出ます。

[yureighost]

これでもいまいちよくわかりませんね。
000
010
000
これで周囲囲むのに4本いるというのはわかりましたが、
000
011
000
こうだとすると棒が共有されてるのは1本で７本必要になるのではないのですかね。

[Zuishin]

このように終端データを追加してアルゴリズムを単純化させる手法を「番兵」と言います。
https://ja.wikipedia.org/wiki/%E7%95%AA%E5%85%B5

[momon-ga]

例２は、重なってるのが４か所だと思いますが、なぜ３？
あ、例が、修正された。

[Zuishin]

yureighost さん、1 を囲む棒、つまり 1 の塊と外界を分けるボーダーだと思うので、1 と 1 の間に棒はないと思います。

[yureighost]

Zuishinさん
あ、なるほど、1同士の間には棒はいらないってことですか。

[fana]

「重なっている分」を引く　みたいな変に工夫した(?)考え方をせずとも，
単純にカウントしていけばよい，すなわち，
「棒を置ける箇所すべてに関して，そこに棒を置くかどうかを判断すればいい」と考えたらどうですか．

行き着く結果（隣接要素の値が異なる箇所の個数を数えるだけの話になる）は一緒でしょうが，「考え方」として．）

Answer 1

特に気の利いたアルゴリズムは使っていない単純な解法です。
現在処理している座標が'1'の場合に棒に4加算し、
更に左と上それぞれの座標をチェックしてそこが'1'なら棒を2本減算します。

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

    int heigt = sc.nextInt();   //高さを取得
    int width = sc.nextInt();   //幅を取得h);
    // 高さ・幅入力の改行入力を捨てる
    sc.nextLine();

    //花壇の情報を1文字ずつ配列に格納していく
    char[][] flower = new char[heigt][width];
    for (int i = 0; i < heigt; i++){
        flower[i] = sc.nextLine().toCharArray();
    }

    // 棒の数
    int barCnt = 0;
    for (int i = 0; i < flower.length; i++) {
        char[] cs = flower[i];
        for (int j = 0; j < cs.length; j++) {
            char c = cs[j];
            // 現在座標が'1'の場合
            if (c == '1') {
                // 棒の数に4本加算する
                barCnt += 4;
                // 上座標が'1'の場合
                if (i > 0 && flower[i - 1][j] == '1') {
                    // 棒の数から2本減算する
                    barCnt -= 2;
                }
                // 左座標が'1'の場合
                if (j > 0 && cs[j -1] == '1') {
                    // 棒の数から2本減算する
                    barCnt -= 2;
                }
            }
        }
    }
    System.out.println("棒の数:" + barCnt);
    sc.close();
}

Comments

[kinako_make]

ありがとうございます。
トレースして、ゆっくり考えてみます。

[kinako_make]

やっと理解できました！
char型配列が全然わかっていなかったことがわかりました。（多次元配列含め）
条件式も私がやりたかったことそのものでした。
自分ではどうやって条件式を書けばいいかわからなっかので（多次元配列の理解ができてなかったので）
とても勉強になりました。
ありがとうございました！

Answer 2

類似の問題で、「島がいくつあるのか」という問題があります。
1を陸地、0を海に見立て、陸続きの島がいくつ存在するかを数える問題です。
この問題の場合、代表的な解法として、ある陸地から隣接する地形を幅優先探索で、訪問済みのフラグを立てながら陸続きを調べる、というものがあります。
このとき、陸地から海または盤外に出ようとする回数を数えれば、それがすなわち必要な棒の数ということになります。

Comments

[kinako_make]

そのような似た問題もあるのですね。
とても考え方の参考になりました。
ありがとうございます。

Answer 3

ロジックは、すでに回答済みなので、以下について

ループの中で要素数が一致するのを数えようと思ったのですが…timelimit exceededになりました。

実際に自分で動かしてみた方がよいです。
または、動かしたあとに修正したなら再実行して動作確認することをオススメします。

iがカウントアップされないので、無限ループですね。

        for (int i = 0; i < heigt; ){
            for (int j = 0; j < width; j++ ){
                if(flg[i][j] == 0 && "#".equals(flower[i][j])){

Comments

[kinako_make]

本当ですね。
なんでそこだけ抜けたのかわかりませんが、思い込みで気づけませんでした。
ご指摘ありがとうございます！