AOJ 1130 Red and Black Time Limit : 1 sec, Memory Limit : 65536 KB

AOJ_1130_bfs.cpp

// 横型探索
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int w, h;
int mx[] = {0, 0, -1, 1};
int my[] = {-1, 1, 0, 0};

int main() {
    while ( true ) {
        int x, y, cnt = 0;
        cin >> w >> h;
        if ( w == 0 && h == 0 ) break;

        vector<string> v(h);
        queue<int> s;

        for ( int i = 0; i < h; i++ ) {
            cin >> v[i];

            // @の座標を記録
            for ( int j = 0; j < v[i].size(); j++ ) {
                if ( v[i][j] == '@' ) {
                    y = i;
                    x = j;
                }
            }
        }

        // キューにスタート地点を追加
        s.push(x);
        s.push(y);

        while(!s.empty()) {
            x = s.front(); s.pop();
            y = s.front(); s.pop();

            for ( int i = 0; i < 4; i++ ) {
                int nx = x + mx[i], ny = y + my[i];
                if ( 0 <= nx && nx < w && 0 <= ny && ny < h && v[ny][nx] == '.' ) {
                    v[ny][nx] = '#';
                    s.push(nx);
                    s.push(ny);
                }
            }
            cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}