PKU Judge Online 2386 Lake Counting

■2386 Lake Counting

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

view plainprint?

1. package p2386;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     final int INF=1<<28;  
17.     final double EPS=1e-9;  
18.   
19.     int n, m;  
20.     int[][] a;  
21.     boolean[][] f;  
22.   
23.     void run(){  
24.         n=sc.nextInt();  
25.         m=sc.nextInt();  
26.         a=new int[n][m];  
27.         f=new boolean[n][m];  
28.         for(int j=0; j<n; j++){  
29.             String s=sc.next();  
30.             for(int i=0; i<m; i++){  
31.                 a[j][i]=s.charAt(i)=='.'?0:1;  
32.             }  
33.         }  
34.         int ans=0;  
35.         for(int j=0; j<n; j++){  
36.             for(int i=0; i<m; i++){  
37.                 if(a[j][i]==1&&!f[j][i]){  
38.                     ans++;  
39.                     visit(i, j);  
40.                 }  
41.             }  
42.         }  
43.         println(ans+"");  
44.     }  
45.   
46.     void visit(int x, int y){  
47.         f[y][x]=true;  
48.         for(int j=-1; j<=1; j++){  
49.             int y2=y+j;  
50.             if(y2<0||y2>=n)  
51.                 continue;  
52.             for(int i=-1; i<=1; i++){  
53.                 int x2=x+i;  
54.                 if(x2<0||x2>=m)  
55.                     continue;  
56.                 if(a[y2][x2]==1&&!f[y2][x2]){  
57.                     visit(x2, y2);  
58.                 }  
59.             }  
60.         }  
61.     }  
62.   
63.     void print(String s){  
64.         System.out.print(s);  
65.     }  
66.   
67.     void println(String s){  
68.         System.out.println(s);  
69.     }  
70.   
71.     public static void main(String[] args){  
72.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
73.         new Main().run();  
74.     }  
75. }  

package p2386;

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

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

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

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

    int n, m;
    int[][] a;
    boolean[][] f;

    void run(){
        n=sc.nextInt();
        m=sc.nextInt();
        a=new int[n][m];
        f=new boolean[n][m];
        for(int j=0; j<n; j++){
            String s=sc.next();
            for(int i=0; i<m; i++){
                a[j][i]=s.charAt(i)=='.'?0:1;
            }
        }
        int ans=0;
        for(int j=0; j<n; j++){
            for(int i=0; i<m; i++){
                if(a[j][i]==1&&!f[j][i]){
                    ans++;
                    visit(i, j);
                }
            }
        }
        println(ans+"");
    }

    void visit(int x, int y){
        f[y][x]=true;
        for(int j=-1; j<=1; j++){
            int y2=y+j;
            if(y2<0||y2>=n)
                continue;
            for(int i=-1; i<=1; i++){
                int x2=x+i;
                if(x2<0||x2>=m)
                    continue;
                if(a[y2][x2]==1&&!f[y2][x2]){
                    visit(x2, y2);
                }
            }
        }
    }

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