本质上就是求图的连通分量的个数。利用栈实现图的遍历。没有使用图的递归
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
62
63
64
65
66
67
68
69
70
71
| import java.util.Scanner;
import java.util.Stack;
public class Main {
static class Node {
int x;
int y;
int value;
public Node(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] map = new int[m][n];
int[][] visited = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = sc.nextInt();
visited[i][j] = 0;
}
}
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] != 1 && map[i][j] == 1) {
count++;
visited[i][j] = 1;
Node beginNode = new Node(i, j, map[i][j]);
Stack<Node> stack = new Stack<>();
stack.push(beginNode);
while (!stack.isEmpty()) {
Node node = stack.peek();
if (node.x + 1 < m && map[node.x + 1][node.y] == 1 && visited[node.x + 1][node.y] == 0) {
visited[node.x + 1][node.y] = 1;
Node node1 = new Node(node.x + 1, node.y, 1);
stack.push(node1);
} else if (node.y + 1 < n && map[node.x][node.y + 1] == 1 && visited[node.x][node.y + 1] == 0) {
visited[node.x][node.y + 1] = 1;
Node node1 = new Node(node.x, node.y + 1, 1);
stack.push(node1);
} else if (node.x - 1 >= 0 && map[node.x - 1][node.y] == 1 && visited[node.x - 1][node.y] == 0) {
visited[node.x - 1][node.y] = 1;
Node node1 = new Node(node.x - 1, node.y, 1);
stack.push(node1);
} else if (node.y - 1 >= 0 && map[node.x][node.y - 1] == 1 && visited[node.x][node.y - 1] == 0) {
visited[node.x][node.y - 1] = 1;
Node node1 = new Node(node.x, node.y - 1, 1);
stack.push(node1);
} else {
stack.pop();
}
}
}
}
}
System.out.println(count);
}
}
|
本文地址：
http://byejd.github.io/2019/11/20/leetcode-200.%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F/