

競技プログラミングの過去問を解いているのですがテストケースで期待した出力をしません。  
なぜでしょうか?  
この問題は全探索の問題な感じなので深さ優先探索を使って解こうとしていますが答えと違う値が表示されてしまいます。

> Problem B: 島はいくつある？
>
> この問題では，同じ大きさの正方形に区切られたメッシュ状の地図が与えられる．  
>  この地図は，ある海域を表しており，各正方形の領域が陸または海に対応する． 図B-1は地図の一例である．
>
>
> [![図b-1](https://i.stack.imgur.com/jQPNd.png)](https://i.stack.imgur.com/jQPNd.png)  
>  図B-1：ある海域の地図
>
> 陸に対応する二つの正方形領域が，地図上で縦，横または斜め方向に隣接しているなら，一方から他方へ歩いて行くことができる．  
>  陸に対応する二つの領域が同じ島に属するのは，一方から他方へ（一般には別の陸地を経由して）歩いて行ける時であり，またその時のみである．  
>  なお，この地図の海域は海で囲まれており，その外側へ歩いて出ることはできない．
>
> 与えられた地図を読み取り，この海域に島がいくつあるか数えるプログラムを作成して欲しい． たとえば，図B-1の地図には，全部で三つの島がある．  
>  Input
>
> 入力はデータセットの列であり，各データセットは次のような形式で与えられる．
[code]

>     w h
>     c1,1 c1,2 ... c1,w
>     c2,1 c2,2 ... c2,w
>     ...
>     ch,1 ch,2 ... ch,w
>  
[/code]

>
> w と h は地図の幅と高さを表す50以下の正の整数であり，地図は w×h 個の同じ大きさの正方形から構成される． w と h  
>  の間は空白文字1個で区切られる．
>
> ci, j は，0 または 1 であり，空白文字1個で区切られる． ci, j = 0 なら，地図上で左から i 番目，上か ら j  
>  番目の正方形は海であり，ci, j = 1 なら陸である．
>
> 入力の終わりは，空白文字1個で区切られた2個のゼロのみからなる行で表される．
[code]

    #include <bits/stdc++.h>
    
    int dx[] = {1, 0, -1, 1, -1, 1, 0, -1};
    int dy[] = {1, 1, 1, 0, 0, -1, -1, -1};
    int w, h, c;
    
    void dfs(int x, int y, std::vector<std::vector<int>> &map, std::vector<std::vector<bool>>& visited, int& c) {
        bool new_land; 
        if (visited[y][x]) { // visited contains whether already visited.
            return;
        }
        visited[y][x] = true;
        if (map[y][x] == 1) {
            new_land = true; // this is may new land.
        }
        else {
            new_land = false; // this is sea
        }
        for (int i = 0; i < 8; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (cx >= w || cx < 0 || cy < 0 || cy >= h) {
                continue;
            }
            if (map[cy][cx] == 1 && visited[cy][cx]) {
                // this land is connected by another land that already visited(counted).
                new_land = false;
            }
        }
        if (new_land) { // if this land is new one: increment counter (int c);
            c++;
        }
        for (int i = 0; i < 8; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (cx >= w || cx < 0 || cy >= h || cy < 0 || visited[cy][cx]) {
                continue;
            }
            dfs(cx, cy, map, visited, c);
        }
    }
    
    
    
    int main() {
        while (true) {
            std::cin >> w >> h;
            if (w == 0 && h == 0) {
                break;
            }
            c = 0; // reset counter for new map;
            std::vector<std::vector<int>> vec(h, std::vector<int>(w, 0));
            std::vector<std::vector<bool>> bools(h, std::vector<bool>(w, false));
            for (int i = 0; i < h; i++) {
                for (int p = 0; p < w; p++) {
                    std::cin >> vec[i][p];
                }
            }
            dfs(0, 0, vec, bools, c);
            std::cout << c << std::endl;
        }
    }
    
[/code]


CC BY-SA 4.0
2019-05-25T03:48:04.363
55234
2019-05-25T07:55:28.050
2019-05-25T04:41:35.577
19110
5246
question
c++ アルゴリズム
深さ優先探索の問題(競技プログラミングの練習)


既にカウント済みの島かどうかを判定する

[code]

        if (map[cy][cx] == 1 && visited[cy][cx]) {
            // this land is connected by another land that already visited(counted).
            new_land = false;
        }
    
[/code]

このコードが現状では不十分です。  
例えば

[code]

    3 3
    1 1 1
    0 0 1
    0 0 1
    
[/code]

こういうテストケースで、x: 0, y: 0 の時と x: 2, y: 2 の二度、島をカウントしてしまいます。(x: 2, y: 2
の時、map[1][2] == 1だが visited[1][2] は false)

もう一つ例を挙げると

[code]

    3 5
    1 0 1
    1 0 1
    1 0 1
    1 0 1
    0 1 0
    
[/code]

こういったテストケースでは、x: 1, y: 4 を探索するまで、x: 0, y: 0 と x: 2, y: 0
が同じ島であると判断できません。この例のように、遠く離れたマスが陸地かどうかを調べるまで近くの陸地が同じ島なのかどうか判断することはできない場合もあります。  
つまり今のコードのような流れで、隣接するマスだけを見て既にカウントされた島かどうか判断することは根本的に無理です。全体的な流れを見直さないといけません。


CC BY-SA 4.0
2019-05-25T07:55:28.050
55237
2019-05-25T07:55:28.050
33033
55234
answer