fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. public class Main {
  7.     static public int[][] map; // [y][x] 가 됨.
  8.     static public boolean[][] visited; //마찬가지로 [y][x]
  9.     static public LinkedList<ArrayList<Integer>> points;
  10.     static public int count =0;
  11.  
  12.     static public int[] gx = {1,-1,0,0};
  13.     static public int[] gy = {0,0,-1,1};
  14.     static public int  map_x_size=0;
  15.     static public int  map_y_size=0;
  16.  
  17.     public static void main(String[] args) throws IOException {
  18.         BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  19.  
  20.         int test_case = Integer.parseInt(bufferedReader.readLine());
  21.         LinkedList<Integer> answer = new LinkedList<>();
  22.  
  23.         while (test_case!=0) {
  24.             String[] t = bufferedReader.readLine().split(" ");
  25.  
  26.             count=0;
  27.             map_x_size = Integer.parseInt(t[0]);
  28.             map_y_size = Integer.parseInt(t[1]);
  29.             int K = Integer.parseInt(t[2]);
  30.  
  31.             map = new int[map_y_size+1][map_x_size+1];
  32.             visited = new boolean[map_y_size+1][map_x_size+1];
  33.             points = new LinkedList<>();
  34.  
  35.             for (int i = 0; i < K; i++) {
  36.                 String[] s = bufferedReader.readLine().split(" ");
  37.                 int a = Integer.parseInt(s[0]);
  38.                 int b = Integer.parseInt(s[1]);
  39.  
  40.                 map[b][a] = 1;
  41.  
  42.                 ArrayList<Integer> p = new ArrayList<>();
  43.                 p.add(b);
  44.                 p.add(a); //points 안에 배추의 위치가 { {y1,x1}, {y2,x2}, ...  }이렇게 저장됨
  45.  
  46.                 points.add(p);
  47.             }
  48.  
  49.             while (points.size() != 0) { //만약 배추가 아예 없는 밭에서는 그냥 while문 실행 없이 초기에 빠져나감 -> 에러 없음
  50.                 ArrayList<Integer> xy = points.get(0);
  51.  
  52.                 int x = xy.get(1);
  53.                 int y = xy.get(0);
  54.  
  55.                 DFS(y, x);
  56.  
  57.                 count++;
  58.  
  59.             }
  60.  
  61.             test_case--;
  62.             answer.add(count);
  63.         }
  64.         for (int i: answer)
  65.             System.out.println(i);
  66.     }
  67.  
  68.     static public void DFS(int y,int x){
  69.         remove_from_points(y,x);
  70.  
  71.         visited[y][x] = true;
  72.  
  73.         for (int i =0; i<4; i++){
  74.             int next_y = y+gy[i];
  75.             int next_x = x+gx[i];
  76.             if(next_x<0 || next_y<0 || next_y>map_y_size-1 || next_x>map_x_size-1 ) continue;
  77.             if(map[next_y][next_x]==1){
  78.                 if(visited[next_y][next_x]==false){
  79.                     DFS(next_y,next_x);
  80.                 }
  81.             }
  82.         }
  83.     }
  84.  
  85.     static public void remove_from_points(int y, int x){
  86.         ArrayList<Integer> xy = new ArrayList<>();
  87.         xy.add(y); xy.add(x); 
  88.         int  ct = 0; 
  89.  
  90.         for (Iterator<ArrayList<Integer>> iterator = points.iterator(); iterator.hasNext();){
  91.             ArrayList<Integer> al = iterator.next();
  92.             if(al.containsAll(xy)){
  93.                 iterator.remove(); 
  94.                 break;
  95.             }
  96.         }
  97.     }
  98. }
Success #stdin #stdout 0.09s 51300KB
comments (?)
stdin
copy 
1
10 10 4
1 2
3 1
1 3
4 1
stdout
copy 
3
https://ideone.com/eXnuYz
language:
Java (HotSpot 12)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!