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; } } }