poj1979

poj1979.md

Poj 1979

簡單 dfs

Code

#include <iostream>
#include <stack>
#include <cstring>
#include <utility>

using namespace std;

int data[20][20];

int dfs(const int W, const int H, const int sr, const int sc) {
    stack< pair<int, int> > st;
    bool added[H][W];
    memset(added, false, sizeof(added));

    added[sr][sc] = true;
    st.push(pair<int, int>(sr, sc));

    int cnt = 0;
    while (!st.empty()) {
        pair<int, int> top = st.top();
        st.pop();

        cnt++;

        int row = top.first;
        int col = top.second;

        int delta_row[4] = {+1, -1, 0, 0};
        int delta_col[4] = {0, 0, +1, -1};
        for (int i=0; i<4; i++) {
            int new_row = row + delta_row[i];
            int new_col = col + delta_col[i];

            if (0 <= new_row && new_row < H && 0 <= new_col && new_col < W) {
                if (data[new_row][new_col] == 1 && !added[new_row][new_col]) {
                    st.push(pair<int, int>(new_row, new_col));
                    added[new_row][new_col] = true;
                }
            }
        }
    }

    return cnt;
}

int main() {
    int W, H;
    while (cin >> W >> H) {
        if (W == 0 && H == 0) break;

        memset(data, -1, sizeof(data));

        int start_row, start_col;

        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                char inp;
                cin >> inp;
                data[i][j] = ((inp == '#') ? 0 : 1);
                if (inp == '@') {
                    start_row = i;
                    start_col = j;
                }
            }
        }

        cout << dfs(W, H, start_row, start_col) << "\n";
    }

    return 0;
}