ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1211 Trapezoids

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1211

'*'で台形が複数与えられます。
(台形の上底と下底はx軸に対して平行です)
面積 m の台形が n 個あるか(複数ある)を求める問題です。


・解法
やるだけ問題です。

上底と下底、そして高さを再帰的に探索して求めることができます。
あとはmapなどを用いて台形の面積とその個数を保存しておきます。


ソースコード

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;

static const int dx[] = {1,-1,0,0,1,1,-1,-1};
static const int dy[] = {0,0,1,-1,1,-1,1,-1};

int h,tx,ty;
char G[1000][80];
bool used[1000][80];
map<int, int> ans;


void init(){
   ans.clear();
   memset(used,false,sizeof(used));

   for(int i = 0 ; i < 1000 ; i++){
      for(int j = 0 ; j < 80 ; j++){
         G[i][j] = ' ';
      }
   }
}


int move_x(int x, int y){
   tx = x;
   ty = y;
   for(int j = -1 ; j <= 1 ; j++){
      if(x+1 < h && 0 <= y+j && y+j < 80 && G[x+1][y+j]=='*')return move_x(x+1, y+j) + 1;
   }
   return 1;
}


int move_y(int x, int y){
   tx = x;
   ty = y;
   if(y+1 < 80 && G[x][y+1]=='*')return move_y(x, y+1) + 1;
   return 1;
}


void del(int x, int y){
   used[x][y] = true;
   for(int k = 0 ; k < 8 ; k++){
      int nx = x + dx[k];
      int ny = y + dy[k];
      if(0<=nx && nx<h && 0<=ny && ny<80 && G[nx][ny]=='*' && !used[nx][ny]) del(nx,ny);
   }
}


int main(){
   int T = 0;
   while(cin >> h){
      if(h==0)break;

      if(T++!=0)cout << "----------" << endl;
      cin.ignore();
      init();

      for(int i = 0 ; i < h ; i++){
         string s;
         getline(cin, s);
	 
         for(int j = 0 ; j < s.size() ; j++){
            G[i][j] = s[j];
         }
      }
      
      for(int i = 0 ; i < h ; i++){
         for(int j = 0 ; j < 80 ; j++){
            if(G[i][j]=='*' && !used[i][j]){
               int ubase = move_y(i, j);//upeer base
               int height = move_x(i, j);
               int lbase = move_y(tx, ty);//lower base
               ans[(ubase + lbase) * height / 2]++;
               del(i,j);
            }
         }
      }

      for(map<int,int>::iterator it = ans.begin() ; it != ans.end() ; it++){
         cout << (*it).first << " " << (*it).second << endl;
      }
   }
   return 0;
}