結果

問題 No.697 池の数はいくつか
ユーザー はにはにはにはに
提出日時 2025-01-06 23:22:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,532 bytes
コンパイル時間 1,201 ms
コンパイル使用メモリ 108,516 KB
実行使用メモリ 713,252 KB
最終ジャッジ日時 2025-01-06 23:22:59
合計ジャッジ時間 49,415 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,768 KB
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 1 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,820 KB
testcase_12 AC 1 ms
6,820 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 1 ms
6,816 KB
testcase_15 AC 1 ms
6,816 KB
testcase_16 AC 1 ms
6,816 KB
testcase_17 AC 2 ms
6,820 KB
testcase_18 AC 1 ms
6,816 KB
testcase_19 AC 1 ms
6,816 KB
testcase_20 AC 1 ms
6,816 KB
testcase_21 AC 1 ms
6,820 KB
testcase_22 AC 1 ms
6,820 KB
testcase_23 AC 1 ms
6,820 KB
testcase_24 AC 771 ms
58,240 KB
testcase_25 AC 802 ms
58,240 KB
testcase_26 AC 786 ms
58,240 KB
testcase_27 AC 768 ms
58,112 KB
testcase_28 AC 804 ms
58,240 KB
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int main() {
    int h, w;
    cin >> h >> w;

    vector<vector<string>> grid(h);
    for (int i = 0; i < h; ++i) {
        grid[i].resize(w);
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
        }
    }

    set<pair<int, int>> sensor;
    for (int j = 0; j < h; ++j) {
        for (int i = 0; i < w; ++i) {
            if (grid[j][i] == "1") {
                sensor.insert({i, j});
            }
        }
    }

    int count = 0;
    set<pair<int, int>> visited;
    while (!sensor.empty()) {
        queue<pair<int, int>> q;
        q.push(*sensor.begin());
        sensor.erase(sensor.begin()); 

        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            
            if (sensor.count({x,y})){
                sensor.erase({x,y});
            }

            int dx[] = {0, 0, 1, -1};
            int dy[] = {1, -1, 0, 0};

            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
                if (grid[ny][nx] == "0") continue;
                if(visited.count({nx, ny}) == 0 && grid[ny][nx] == "1"){
                    visited.insert({nx, ny});
                    q.push({nx, ny});
                }
            }
        }
        count++;
    }
    
    cout << count << endl;
    return 0;
}
0