Aizu Online Judge 0118 Property Distribution

■0118 Property Distribution

再帰を使うとおそらくスタックオーバーフローするので，キューを使ってBFS．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. public class Main{  
7.   
8.  Scanner sc=new Scanner(System.in);;  
9.   
10.  int INF=1<<28;  
11.  double EPS=1e-9;  
12.   
13.  int[][] a;  
14.  int w, h;  
15.  boolean[][] visited;  
16.   
17.  void run(){  
18.   for(;;){  
19.    h=sc.nextInt();  
20.    w=sc.nextInt();  
21.    if((h|w)==0){  
22.     break;  
23.    }  
24.    a=new int[h][w];  
25.    visited=new boolean[h][w];  
26.    for(int j=0; j<h; j++){  
27.     String s=sc.next();  
28.     for(int i=0; i<w; i++){  
29.      switch(s.charAt(i)){  
30.      case '@':  
31.       a[j][i]=0;  
32.       break;  
33.      case '#':  
34.       a[j][i]=1;  
35.       break;  
36.      case '*':  
37.       a[j][i]=2;  
38.       break;  
39.      }  
40.     }  
41.    }  
42.    solve();  
43.   }  
44.  }  
45.   
46.  void solve(){  
47.   int ans=0;  
48.   for(int j=0; j<h; j++){  
49.    for(int i=0; i<w; i++){  
50.     if(!visited[j][i]){  
51.      ans++;  
52.      bfs(i, j);  
53.     }  
54.    }  
55.   }  
56.   println(ans+"");  
57.  }  
58.   
59.  void bfs(int x, int y){  
60.   LinkedList<P> que=new LinkedList<P>();  
61.   que.offer(new P(x, y));  
62.   visited[y][x]=true;  
63.   int[] dx={0, 0, -1, 1};  
64.   int[] dy={-1, 1, 0, 0};  
65.   for(; !que.isEmpty();){  
66.    P p=que.poll();  
67.    for(int i=0; i<4; i++){  
68.     P q=new P(p.x+dx[i], p.y+dy[i]);  
69.     if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&!visited[q.y][q.x]  
70.       &&a[p.y][p.x]==a[q.y][q.x]){  
71.      que.offer(q);  
72.      visited[q.y][q.x]=true;  
73.     }  
74.    }  
75.   }  
76.  }  
77.   
78.  class P{  
79.   int x, y;  
80.   
81.   P(int x, int y){  
82.    this.x=x;  
83.    this.y=y;  
84.   }  
85.  }  
86.   
87.  void debug(Object... os){  
88.   System.err.println(Arrays.deepToString(os));  
89.  }  
90.   
91.  void print(String s){  
92.   System.out.print(s);  
93.  }  
94.   
95.  void println(String s){  
96.   System.out.println(s);  
97.  }  
98.   
99.  public static void main(String[] args){  
100.   new Main().run();  
101.  }  
102. }  

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

public class Main{

 Scanner sc=new Scanner(System.in);;

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

 int[][] a;
 int w, h;
 boolean[][] visited;

 void run(){
  for(;;){
   h=sc.nextInt();
   w=sc.nextInt();
   if((h|w)==0){
    break;
   }
   a=new int[h][w];
   visited=new boolean[h][w];
   for(int j=0; j<h; j++){
    String s=sc.next();
    for(int i=0; i<w; i++){
     switch(s.charAt(i)){
     case '@':
      a[j][i]=0;
      break;
     case '#':
      a[j][i]=1;
      break;
     case '*':
      a[j][i]=2;
      break;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  int ans=0;
  for(int j=0; j<h; j++){
   for(int i=0; i<w; i++){
    if(!visited[j][i]){
     ans++;
     bfs(i, j);
    }
   }
  }
  println(ans+"");
 }

 void bfs(int x, int y){
  LinkedList<P> que=new LinkedList<P>();
  que.offer(new P(x, y));
  visited[y][x]=true;
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};
  for(; !que.isEmpty();){
   P p=que.poll();
   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<w&&q.y>=0&&q.y<h&&!visited[q.y][q.x]
      &&a[p.y][p.x]==a[q.y][q.x]){
     que.offer(q);
     visited[q.y][q.x]=true;
    }
   }
  }
 }

 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){
  new Main().run();
 }
}