题解 | 挡住洪水

#include <iostream>
#include <vector>
using namespace std;
struct Pt {
    int y;
    int x;
};
int main() {
    int xLen,yLen;
    cin >> yLen >> xLen;
    vector<string> data(yLen);
    for(auto& s : data) {
        cin >> s;
    }

    vector<vector<bool>> visited(yLen,vector<bool>(xLen));
    vector<vector<int>> flag(yLen,vector<int>(xLen, -1));
    vector<Pt> stack;
    // 上下
    for(auto i : {0,yLen-1}) {
        for(auto j = 0; j < xLen; ++j) {
            stack.push_back(Pt{i,j});
            flag[i][j] = 0;
        }
    }
    // 左右
    for(auto j : {0,xLen-1}) {
        for(auto i = 1; i < yLen-1; ++i) {
            stack.push_back(Pt{i,j});
            flag[i][j] = 0;
        }
    }
    vector<Pt> round = {
        {-1,0}, {1,0}, {0,-1}, {0,1}
    };
    while(stack.size()) {
        auto pt = stack.back();
        stack.pop_back();
        if(visited[pt.y][pt.x]) {
            continue;
        }
        visited[pt.y][pt.x] = true;
        if(data[pt.y][pt.x] == '*') {
            continue;
        }
        auto curFlag = flag[pt.y][pt.x];
        for(auto& off : round) {
            auto x = pt.x + off.x;
            auto y = pt.y + off.y;
            if(x < 0 || y < 0 || x >= xLen || y >= yLen) {
                continue;
            }
            if(visited[y][x]) {
                continue;
            }
            if(data[y][x] == '0') {
                flag[y][x] = curFlag + 1;
                stack.push_back(Pt{y,x});
            }
        }
    }
    // for(auto& vec : flag) {
    //     for(auto v : vec) {
    //         cout << v << " ";
    //     }
    //     cout << endl;
    // }
    //cout << endl;
    int total = 0;
    for(auto i = 0; i < yLen; ++i) {
        for(auto j = 0; j < xLen; ++j) {
            if(data[i][j] == '0' && flag[i][j] == -1) {
                total++;
            }
        }
    }
    cout << total << endl;
}
// 64 位输出请用 printf("%lld")