深搜之水池数目

数目"/>

深搜之水池数目

RT  .php?pid=27

直接贴代码：

import java.util.*;
import java.io.*;


public class Main {
private static int[][] d = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();// 表示有n组测试数据
while (N-- > 0) {
int m = sc.nextInt();// 表示行数
int n = sc.nextInt();// 表示列数
int count = 0;
int[][] map = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
map[i][j] = sc.nextInt();// 1表示有水池 0表示没有水池
}


for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (map[i][j] == 1) {
count++;
DFS(i, j, map,m,n);

}

}
System.out.println(count);


}


}


public static void DFS(int x0, int y0, int[][] map,int m,int n) {
map[x0][y0] = -1; // 表示已经访问过
for (int i = 0; i < 4; i++) {
int x1=x0+d[i][0];
int y1=y0+d[i][1];
if(x1>=0&&x1<m&&y1>=0&&y1<n&&map[x1][y1]==1)
{
DFS(x1, y1, map,m,n);
}


}


}
}