AOJ 1130 Red and Black

問題

Red and Black | Aizu Online Judge

WxHのフィールドの中でスタート地点から四方に移動する。黒のタイルの上だけを通って移動できるタイルの数を求めよ。

方針

スタート地点からdfsして到達可能なタイルをメモ。タイルの数を最後に数える。

コード

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define rep(i, n) for(int i=0; i<(n); ++i)

char field[21][21];
char visit[21][21];
int dx[]= {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int W, H;
void dfs(int y, int x) {
    visit[y][x] = 1;
    rep(i, 4) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(field[ny][nx] == '.' && visit[ny][nx] == 0 &&
               nx >= 0 && nx < W && ny >= 0 && ny < H) {
            dfs(ny, nx);
        }
    }
}
int main(void){
    while(cin >> W >> H && W) {
        int y, x;
        rep(i, H) rep(j, W){
            cin >> field[i][j];
            if(field[i][j] == '@') y = i, x = j;
        }
        memset(visit, 0, sizeof(visit));
        dfs(y, x);
        int ans = 0;
        rep(i, H) rep(j, W){
            ans += visit[i][j];
        }
        cout << ans << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1889713

反省

• カウントもdfs関数の中でやった方がきれいなコードになった