-1

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

Problem B: 島はいくつある?

この問題では,同じ大きさの正方形に区切られたメッシュ状の地図が与えられる.
この地図は,ある海域を表しており,各正方形の領域が陸または海に対応する. 図B-1は地図の一例である.

図b-1
図B-1:ある海域の地図

陸に対応する二つの正方形領域が,地図上で縦,横または斜め方向に隣接しているなら,一方から他方へ歩いて行くことができる.
陸に対応する二つの領域が同じ島に属するのは,一方から他方へ(一般には別の陸地を経由して)歩いて行ける時であり,またその時のみである.
なお,この地図の海域は海で囲まれており,その外側へ歩いて出ることはできない.

与えられた地図を読み取り,この海域に島がいくつあるか数えるプログラムを作成して欲しい. たとえば,図B-1の地図には,全部で三つの島がある.
Input

入力はデータセットの列であり,各データセットは次のような形式で与えられる.

w h
c1,1 c1,2 ... c1,w
c2,1 c2,2 ... c2,w
...
ch,1 ch,2 ... ch,w

w と h は地図の幅と高さを表す50以下の正の整数であり,地図は w×h 個の同じ大きさの正方形から構成される. w と h
の間は空白文字1個で区切られる.

ci, j は,0 または 1 であり,空白文字1個で区切られる. ci, j = 0 なら,地図上で左から i 番目,上か ら j
番目の正方形は海であり,ci, j = 1 なら陸である.

入力の終わりは,空白文字1個で区切られた2個のゼロのみからなる行で表される.

#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;
    }
}
1
  • 4
    問題の著作権にご留意ください。もしこの問題に出典があるのでしたら、適切に示さないと引用になりません。また、おそらく何かしらの競技プログラミングサービスをご利用なのでしょうが、テストケースに通らないといってもどのケースで通らないか分かっているのか分かっていないのかで答える難易度が変わってきます。ご自身でどのようなデバッグをなさったのか具体的に書いてくださった方が回答しやすそうです。
    – nekketsuuu
    Commented 2019年5月25日 4:29

1 件の回答 1

3

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

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

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

3 3
1 1 1
0 0 1
0 0 1

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

もう一つ例を挙げると

3 5
1 0 1
1 0 1
1 0 1
1 0 1
0 1 0

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。