水池数目
时间限制：3000 ms
| 内存限制：65535 KB
难度：4
- 描述
- 南阳理工学院校园里有一些小河和一些湖泊，现在，我们把它们通一看成水池，假设有一张我们学校的某处的地图，这个地图上仅标识了此处是否是水池，现在，你的任务来了，请用计算机算出该地图中共有几个水池。
-
- 输入
-
第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该地图的行数m(0 - 输出
-
输出该地图中水池的个数。
要注意，每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。 - 样例输入
-
2 3 4 1 0 0 0 0 0 1 1 1 1 1 0 5 5 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1
- 样例输出
-
2 3
- 来源
-
[张云聪]原创 - 上传者
-
张云聪 - 分析：
- 这实际上是不相关集的应用
- import
java.awt.Point; - import
java.util.ArrayList; - import
java.util.Scanner; - public
class FindPools_V1 { - public
static void main(String[] args) { - FindPools_V1 findPools_V1 = new
FindPools_V1(); - findPools_V1.solution();
- }
- public
void solution() { - Scanner in = new Scanner(System.in);
- int
groups = in.nextInt(); - for
(int i = 0; i < groups; i++) { - int
height = in.nextInt(); - int
width = in.nextInt(); - int[][] campus = new int[height + 2][width +
2]; - for
(int m = 1; m <= height; m++) { - for
(int n = 1; n <= width; n++) { - campus[m][n] = in.nextInt();
- }
- }
- UnRelatedSet unRelatedSet = new UnRelatedSet(campus,
height, width); - System.out.println(unRelatedSet.sort());
- }
- }
- class
UnRelatedSet { - int[][] campus;
- int
width; - int
height; - ArrayList> itemList;
- public
UnRelatedSet(int[][] campus, int height, int width) { - this.campus = campus;
- this.width = width;
- this.height = height;
- itemList = new ArrayList>();
- }
- //
此方法进行整理成不相关集的操作，返回值为不相关集的总数； - public
int sort() { - for
(int i = 1; i <= height; i++) { - for
(int j = 1; j <= width; j++) { - if
(campus[i][j] == 1) { - ArrayList temp = new ArrayList();
- temp.add(new Point(i, j));
- for
(int k = 0; k < itemList.size(); k++) { - ArrayList temp1 = itemList.get(k);
- if
((campus[i - 1][j] == 1 && temp1 - .contains(new Point(i - 1, j)))
- ||
(campus[i + 1][j] == 1 && temp1 - .contains(new Point(i + 1, j)))
- ||
(campus[i][j - 1] == 1 && temp1 - .contains(new Point(i, j - 1)))
- ||
(campus[i][j + 1] == 1 && temp1 - .contains(new Point(i, j + 1)))) {
- temp.addAll(temp1);
- itemList.remove(temp1);
-
k--; - }
-
- }
- itemList.add(temp);
- }
- }
- }
- return
itemList.size(); - }
- }
- }