AOJ_0118 Property Distribution
問題
解法
あるマスがまだ区画整理されていなければ、
1,区画の総数に1をたす。
2,区画整理したしるしをつける。
3,隣接するマスが(区画整理されていない&&同じ木の種類)ならば区画整理したしるしをつける。
4, 3を再帰的に行う。
区画整理されていないマスがなくなったら区画の総数を出力して終了。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_H = 100, MAX_W = 100; int H, W; int kazyuen[MAX_H][MAX_W]; bool used[MAX_H][MAX_W]; //すでに整理された区画 const int dx[] = {-1, 0, 1, 0}; const int dy[] = { 0, -1, 0, 1}; void solve(int a, int p, int q){ if(used[p][q]) return; if(p < 0 || H <= p || q < 0 || W <= q) return; if(kazyuen[p][q] != a) return; used[p][q] = true; //探索済みのしるし for(int i = 0; i < 4; i++){ //隣接する4方向に探索 solve(a, p + dy[i], q + dx[i]); } } int main(){ char c; while(scanf("%d %d", &H, &W) && H && W){ for(int i = 0; i < H; i++){ scanf("%c", &c); for(int j = 0; j < W; j++){ scanf("%c", &c); if(c == '#'){ kazyuen[i][j] = 0; }else if(c == '@'){ kazyuen[i][j] = 1; }else{ kazyuen[i][j] = 2; } used[i][j] = false; } } int sum = 0; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(!used[i][j]){ //まだ区画が整理されていない sum++; solve(kazyuen[i][j], i, j); } } } printf("%d\n", sum); } return 0; }