题目描述
题目描述:
输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。 如果两个字符“@”所在的格子相邻(横、竖或者对角线方向),就说它们属于同一个八连块。
样例
5 5
@@**@
@**@@
****@
@@***
@**@@
4
思路:
还是使用图的DFS来解决问题
java 代码
import java.util.Scanner;
public class Main {
static char[][] data=new char[50][50];
static int dirx[]= {0,0,-1,1,-1,1,-1,1};
static int diry[]= {-1,1,0,0,-1,1,1,-1};
static int n;
static int m;
static int cnt=0;
public static void dfs(int i, int j) {
if(i<0 || i>=n || j<0 || j>=m) {
return;
}
if(data[i][j]=='*') {
return;
}
data[i][j]='*'; //不用重复找
for(int k=0;k<8;k++) {
int x=i+dirx[k];
int y=j+diry[k];
if( x>=0 && x<n && y>=0 && y<n && data[x][y]=='@'){
dfs(x,y);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine();
for(int i=0;i<n;i++) {
data[i]=sc.nextLine().toCharArray();
}
int cnt=0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(data[i][j]=='@') {
dfs(i,j);
cnt++;
}
}
}
System.out.println(cnt);
}
}