Aizu Online Judge 1211 Trapezoids

■1211 Trapezoids

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

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

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

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

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

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

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

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  int[][] a;  
18.  int c;  
19.  boolean[] wall;  
20.   
21.  void run(){  
22.   for(int k=0;; k++){  
23.    n=sc.nextInt();  
24.    if(n==0){  
25.     break;  
26.    }  
27.    if(k>0){  
28.     println("----------");  
29.    }  
30.    sc.nextLine();  
31.    m=0;  
32.    String[] ss=new String[n];  
33.    for(int i=0; i<n; i++){  
34.     ss[i]=sc.nextLine();  
35.     m=max(m, ss[i].length());  
36.    }  
37.    a=new int[n][m];  
38.    for(int j=0; j<n; j++){  
39.     for(int i=0; i<ss[j].length(); i++){  
40.      a[j][i]=ss[j].charAt(i)=='*'?1:0;  
41.     }  
42.    }  
43.    solve();  
44.   }  
45.  }  
46.   
47.  void solve(){  
48.   c=2;  
49.   wall=new boolean[]{false, true, true};  
50.   for(int j=0; j<n; j++){  
51.    if(a[j][0]==0){  
52.     bfs(0, j);  
53.    }  
54.    if(a[j][m-1]==0){  
55.     bfs(m-1, j);  
56.    }  
57.   }  
58.   for(int i=0; i<m; i++){  
59.    if(a[0][i]==0){  
60.     bfs(i, 0);  
61.    }  
62.    if(a[n-1][i]==0){  
63.     bfs(i, n-1);  
64.    }  
65.   }  
66.   
67.   HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();  
68.   int[] dx={1, 1, 0, -1, -1, -1, 0, 1};  
69.   int[] dy={0, 1, 1, 1, 0, -1, -1, -1};  
70.   for(int j=0; j<n; j++){  
71.    for(int i=0; i<m; i++){  
72.     if(a[j][i]==1){  
73.      int outline=0;  
74.      int d=0;  
75.      int x=i, y=j;  
76.      for(;;){  
77.       outline++;  
78.       a[y][x]=0;  
79.       boolean f=false;  
80.       d=(d+5)%8;  
81.       for(int k=0; k<8; k++, d=(d+1)%8){  
82.        int x2=x+dx[d];  
83.        int y2=y+dy[d];  
84.        if(x2>=0&&x2<m&&y2>=0&&y2<n&&a[y2][x2]==1){  
85.         x=x2;  
86.         y=y2;  
87.         f=true;  
88.         break;  
89.        }  
90.       }  
91.       if(!f){  
92.        break;  
93.       }  
94.      }  
95.      c=-1;  
96.      wall=new boolean[]{false, false, true};  
97.      int area=bfs(x, y);  
98.      if(!map.containsKey(area)){  
99.       map.put(area, 0);  
100.      }  
101.      map.put(area, map.get(area)+1);  
102.   
103.      c=2;  
104.      wall=new boolean[]{false, true, true};  
105.      bfs(x, y);  
106.     }  
107.    }  
108.   }  
109.   Integer[] is=map.keySet().toArray(new Integer[0]);  
110.   sort(is);  
111.   for(int key : is){  
112.    println(key+" "+map.get(key));  
113.   }  
114.  }  
115.   
116.  int bfs(int x, int y){  
117.   int[] dx={0, 0, -1, 1};  
118.   int[] dy={-1, 1, 0, 0};  
119.   LinkedList<P> que=new LinkedList<P>();  
120.   boolean[][] visited=new boolean[n][m];  
121.   que.add(new P(x, y));  
122.   visited[y][x]=true;  
123.   int res=0;  
124.   for(; !que.isEmpty();){  
125.    P p=que.poll();  
126.    if(c>=0){  
127.     a[p.y][p.x]=c;  
128.    }  
129.    res++;  
130.    for(int i=0; i<4; i++){  
131.     P q=new P(p.x+dx[i], p.y+dy[i]);  
132.     if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]  
133.       &&!wall[a[q.y][q.x]]){  
134.      que.add(q);  
135.      visited[q.y][q.x]=true;  
136.     }  
137.    }  
138.   }  
139.   return res;  
140.  }  
141.   
142.  class P{  
143.   int x, y;  
144.   
145.   P(int x, int y){  
146.    this.x=x;  
147.    this.y=y;  
148.   }  
149.  }  
150.   
151.  void debug(Object... os){  
152.   System.err.println(Arrays.deepToString(os));  
153.  }  
154.   
155.  void print(String s){  
156.   System.out.print(s);  
157.  }  
158.   
159.  void println(String s){  
160.   System.out.println(s);  
161.  }  
162.   
163.  public static void main(String[] args){  
164.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
165.   new Main().run();  
166.  }  
167. }  

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