AOJ 1211 Trapezoids

Trapezoids
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1211

問題概要

アスタリスクでかかれた図形がいくつかある。
それぞれの面積を求めよ。

解法

DFSした。
図形の辺の上をぐるっとたどって、高さと上辺と下辺を出して面積を出した。
でも、ふつうにDFSで色塗りすればできそう。

ソース

#include <map>
#include <set>
#include <iostream>
#include <string>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int N = 1000;
enum{
  UP, RIGHT_UP, RIGHT, RIGHT_DOWN, DOWN, LEFT_DOWN, LEFT, LEFT_UP
};

int width, height, H;
string t[N];
set<pair<int, int> > S;

bool invalid(int y, int x){
  if(y < 0 || x < 0)return true;
  if(y >= H || x >= (int)t[y].length())return true;
  return false;
}

void dfs(int state, int y, int x){
  if(invalid(y, x) || t[y][x] != '*')return;
  S.insert(make_pair(y, x));
  if(state >= RIGHT_DOWN && state <= LEFT_DOWN)height++;
  if(state == RIGHT || state == LEFT)width++;
  if(state == RIGHT){
    REP(i, RIGHT, LEFT_DOWN+1){
      int nx = x + dx[i], ny = y+dy[i];
      if(invalid(ny, nx))continue;
      if(t[ny][nx] == '*'){
        if(i != RIGHT)height++;
        dfs(i, ny, nx);
        return;
      }
    }
  }
  if(state == LEFT){
    int d = LEFT;
    while(1){
      int nx = x + dx[d], ny = y+dy[d];
      if(invalid(ny, nx)){
        d++;
        d %= 8;
        if(d == RIGHT)break;
        continue;
      }
      if(t[ny][nx] == '*'){
        dfs(d, ny, nx);
        return;
      }
      d++;
      d %= 8;
      if(d == RIGHT)break;
    }
  }
  int nx = x + dx[state];
  int ny = y + dy[state];
  if(invalid(ny, nx) || t[ny][nx] != '*'){
    if(state >= 3 && state <= 5){
      dfs(LEFT, y, x);
      return;
    }
    return;
  }
  dfs(state, ny, nx);
  return;
}

int main(){
  bool first = true;
  while(cin >> H){
    if(H == 0)break;
    if(!first)cout << "----------" << endl;
    first = false;
    S.clear();
    getline(cin, t[0]);
    rep(i, H){
      getline(cin, t[i]);
    }
    map<int, int> ANS;
    rep(i, H){
      rep(j, t[i].length()){
        if(S.find(make_pair(i, j)) != S.end())continue;
        if(t[i][j] != '*')continue;
        height = width = 0;
        dfs(RIGHT, i, j);
        ANS[height * width]++;
      }
    }
    FOR(it, ANS){
      cout << it->first/2 << ' ' << it->second << endl;
    }
  }
}