Algorithm_Practice/1012.java at master · ktyu/Algorithm_Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
importjava.util.*;

publicclassMain {
staticclassPoint {
intx,y;
Point(intx, inty) {this.x=x; this.y=y;}
 }

publicstaticvoidmain(String[] args) {

Scannersc = newScanner(System.in);

inttcCnt = sc.nextInt();

while(tcCnt-- > 0) {
intm = sc.nextInt();
intn = sc.nextInt();
intk = sc.nextInt();
int[][] map = newint[m][n];

for(inti=0; i<k; i++) {
intx = sc.nextInt();
inty = sc.nextInt();
map[x][y] = 1;
 }

intcnt = 2;
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};

for(inti=0; i<m; i++) {
for(intj=0; j<n; j++) {
if(map[i][j] == 1) {
Queue<Point> q = newLinkedList<>();
q.add(newPoint(i, j));
map[i][j] = cnt;
while(!q.isEmpty()) {
Pointp = q.remove();
for(inta=0; a<4; a++) {
intx = p.x+dx[a];
inty = p.y+dy[a];

if(x<0 || x>=m || y<0 || y>=n)
continue;

if(map[x][y] == 1) {
map[x][y] = cnt;
q.add(newPoint(x, y));
 }
 }
 }
cnt++;
 }
 }
 }

System.out.println(cnt-2);
 }
 }

}