Aizu Online Judge 1211 Trapezoids

■1211 Trapezoids

下のような入力が与えられたとする．

***                     *  *         ********** *   *        *        * *    *       * ***    * *     *      * *  *   * *      *     * *****  * *       *    *        * *        *   ********** *         *             ************

まず，四角形の内部となりえない所をある値（ここでは'-'）で埋める．

-----------***--------- -----------*  *-------- **********-*   *------- *        *-*    *------ * ***    *-*     *----- * *  *   *-*      *---- * *****  *-*       *--- *        *-*        *-- **********-*         *- -----------************

(i, j)が'*'となる(i, j)をラスタスキャン． 輪郭をたどり，たどった点を' 'に変更する．

-----------***--------- -----------*  *-------- -----------*   *------- -        --*    *------ - ***    --*     *----- - *  *   --*      *---- - *****  --*       *--- -        --*        *-- -----------*         *- -----------************

'-'のみを壁として(i, j)からBFS．この時の探索回数が領域の面積．
(i, j)からBFSで0を'-'に塗りつぶしていく

-----------***--------- -----------*  *-------- -----------*   *------- -----------*    *------ --***------*     *----- --*  *-----*      *---- --*****----*       *--- -----------*        *-- -----------*         *- -----------************

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 int[][] a;
 int c;
 boolean[] wall;

 void run(){
  for(int k=0;; k++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   if(k>0){
    println("----------");
   }
   sc.nextLine();
   m=0;
   String[] ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.nextLine();
    m=max(m, ss[i].length());
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<ss[j].length(); i++){
     a[j][i]=ss[j].charAt(i)=='*'?1:0;
    }
   }
   solve();
  }
 }

 void solve(){
  c=2;
  wall=new boolean[]{false, true, true};
  for(int j=0; j<n; j++){
   if(a[j][0]==0){
    bfs(0, j);
   }
   if(a[j][m-1]==0){
    bfs(m-1, j);
   }
  }
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    bfs(i, 0);
   }
   if(a[n-1][i]==0){
    bfs(i, n-1);
   }
  }

  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  int[] dx={1, 1, 0, -1, -1, -1, 0, 1};
  int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    if(a[j][i]==1){
     int outline=0;
     int d=0;
     int x=i, y=j;
     for(;;){
      outline++;
      a[y][x]=0;
      boolean f=false;
      d=(d+5)%8;
      for(int k=0; k<8; k++, d=(d+1)%8){
       int x2=x+dx[d];
       int y2=y+dy[d];
       if(x2>=0&&x2<m&&y2>=0&&y2<n&&a[y2][x2]==1){
        x=x2;
        y=y2;
        f=true;
        break;
       }
      }
      if(!f){
       break;
      }
     }
     c=-1;
     wall=new boolean[]{false, false, true};
     int area=bfs(x, y);
     if(!map.containsKey(area)){
      map.put(area, 0);
     }
     map.put(area, map.get(area)+1);

     c=2;
     wall=new boolean[]{false, true, true};
     bfs(x, y);
    }
   }
  }
  Integer[] is=map.keySet().toArray(new Integer[0]);
  sort(is);
  for(int key : is){
   println(key+" "+map.get(key));
  }
 }

 int bfs(int x, int y){
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[n][m];
  que.add(new P(x, y));
  visited[y][x]=true;
  int res=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(c>=0){
    a[p.y][p.x]=c;
   }
   res++;
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]
      &&!wall[a[q.y][q.x]]){
     que.add(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  return res;
 }

 class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}