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になりました。

```import java.util.*;


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);
    }
}
コード
```

間違っている点や
他の考え方など、ご教授いただければと思います。
よろしくお願いいたします。

Accepted Answer

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

Answer

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

Answer

ロジックは、すでに回答済みなので、以下について

> ループの中で要素数が一致するのを数えようと思ったのですが…timelimit exceededになりました。

実際に自分で動かしてみた方がよいです。
または、動かしたあとに修正したなら再実行して動作確認することをオススメします。

**iがカウントアップされない**ので、無限ループですね。

```java
        for (int i = 0; i < heigt; ){
            for (int j = 0; j < width; j++ ){
                if(flg[i][j] == 0 && "#".equals(flower[i][j])){
```

関連した質問