（Java实现）细胞

细胞

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 8 Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

Input

输入第一行为T，表示有T组测试数据，对于每组测试数据第一行为m和n(1<m,n<100)，表示矩阵的行和列。下面m行是矩阵。

Output

对于每组测试数据，输出矩阵中的细胞个数。

Sample Input

1

4 10

0234500067

1034560500

2045600671

0000000089

Sample Output

4

Author

//思路;题目意思是一片区域内没有一个数字0 那就是一个细胞所以不需要对标记数组清零回溯

import java.util.Scanner;

public class xibao {

	public static int a,b;

	public static boolean [] [] bool;

	public static char [][] num;

	public static void main(String[] args) {

		Scanner sc =new Scanner(System.in);

		 a = sc.nextInt();

		 b = sc.nextInt();

		int sum = 0;

		num = new char [a][b];

		bool = new boolean [a][b];

		for (int i = 0; i < a; i++) {

			String s = sc.next();

			for (int j = 0; j < b; j++) {

				num[i][j]=s.charAt(j);

			}

		}

		for (int i = 0; i < a; i++) {

			for (int j = 0; j < b; j++) {

				if(num[i][j]!='0' && !bool[i][j]){

					sum++;

					dfs(i,j);

				}

			}

		}

		System.out.println(sum);

	}

	public static void dfs(int x,int y){

		 if(x>=a || x<0 || y>=b || y<0 || num[x][y]=='0' || bool[x][y]) return;

		    bool[x][y]=true;

		    dfs(x+1,y);

		    dfs(x,y+1);

		    dfs(x-1,y);

		    dfs(x,y-1);//清除细胞的爆搜部分

	}

}

巴特西

（Java实现）细胞

最新文章

热门文章

巴特西

（Java实现） 细胞

最新文章

热门文章

（Java实现）细胞