AIZU ONLINE JUDGE解いてみた AOJ 1160 島はいくつある？

AOJ 1160 島はいくつある？

問題はこちら

コード

深さ優先探索

#include <iostream>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;


int islandMap[50][50];
bool seen[50][50];


struct Point {
    int y;
    int x;
};

void dfs(const Point& pt, const int& w, const int& h) {

    seen[pt.y][pt.x] = true; // 訪問済み

    // 上下左右斜めに探索可能
    for (int dy = -1; dy <= 1; dy++) {
        for (int dx = -1; dx <= 1; dx++) {
            Point nextPt{ pt.y + dy, pt.x + dx };

            // 範囲内かつ、未訪問かつ、陸地の時にさらなる探索
            if (0 <= nextPt.x && nextPt.x < w && 0 <= nextPt.y && nextPt.y < h && !seen[nextPt.y][nextPt.x] && islandMap[nextPt.y][nextPt.x] == 1) {
                dfs(nextPt, w, h);
            }
        }
    }

}

int main() {
    int w;
    int h;

    while (cin >> w >> h) {
        if (h == 0 || w == 0) break;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> islandMap[i][j];
                seen[i][j] = false; // 未訪問と設定
            }
        }

        // wxhの全ての点から、未訪問の陸地に対してdfsで探索していく
        // 探索できた分カウントする

        int count = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                Point pt{ i,j };

                // 未訪問かつ、陸なら探索
                if (!seen[i][j] && islandMap[i][j] == 1) {
                    // dfs
                    dfs(pt, w, h);

                    count++;
                }
            }
        }

        cout << count << endl;
    }


    return 0;
}

幅優先探索

#include <iostream>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;


int islandMap[50][50];
bool seen[50][50];


struct Point {
    int y;
    int x;
};

int main() {
    int w;
    int h;

    // bfsでやる場合、探索開始点(陸)の周囲を見渡し、陸の点をqueに入れて行けばいいのかな?
    while (cin >> w >> h) {
        if (h == 0 || w == 0) break;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> islandMap[i][j];
                seen[i][j] = false; // 未訪問と設定
            }
        }

        // wxhの全ての点から、未訪問の陸地に対してdfsで探索していく
        // 探索できた分カウントする

        int count = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                Point pt{ i,j };

                // 未訪問かつ、陸なら探索
                if (!seen[i][j] && islandMap[i][j] == 1) {

                    // bfs
                    queue<Point> que;
                    seen[i][j] = true; // (i,j)が初期ノード

                    que.push(pt);

                    // queが空になるまで探索を続ける
                    // 最後の列に幅優先探索が効いていない
                    while (!que.empty()) {
                        Point ptS = que.front();

                        que.pop();

                        // 隣接点を見る
                        for (int dx = -1; dx <= 1; dx++) {
                            for (int dy = -1; dy <= 1; dy++) {
                                Point ptNext = { ptS.y + dy, ptS.x + dx };

                                // 隣接点が範囲内かつ、未訪問かつ、陸
                                if (0 <= ptNext.y && ptNext.y < h && 0 <= ptNext.x && ptNext.x < w && !seen[ptNext.y][ptNext.x] && islandMap[ptNext.y][ptNext.x] == 1) {
                                    seen[ptNext.y][ptNext.x] = true; // 訪問済み
                                    que.push(ptNext); // 次にループで隣接点を中心として探索を行うため、queにpush
                                }
                            }
                        }
                    } // while

                    count++;
                }
            }
        }

        cout << count << endl;
    }

    return 0;
}