背景描述java
ztw同志负责探测地下石油储藏.ztw如今在一块矩形区域探测石油.他经过专业设备,来分析每一个小块中是否蕴藏石油.若是这些蕴藏石油的小方格相邻(横向相邻,纵向相邻,还有对角相邻),那么它们被认为是同一油藏的一部分.在这块矩形区域,可能有不少油藏.你的任务是肯定有多少不一样的油藏.数组
输入测试
输入可能有多个矩形区域(便可能有多组测试)。每一个矩形区域的起始行包含m和n,表示行和列的数量,1<=n,m<=100,若是m=0表示输入的结束,接下来是n行,每行m个字符.每一个字符对应一个小方格,而且要么是‘*’、表明没有油,要么是‘@’,表示有油.(注意多组数据,必要的数组要及时清空~)spa
输出code
对于每个矩形区域,输出油藏的数量.两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。blog
示例输入class
示例输出import
import java.util.Scanner; public class Main{ static int n,m,cnt; static final int N=105; static char map[][]=new char[N][N]; static int dx[]={0,0,1,-1, 1,-1,1,-1}; static int dy[]={1,-1,0,0,1,-1,-1,1}; static void dfs(int x,int y){ if(map[x][y]=='@'){ map[x][y]='*'; } for(int i=0;i<8;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(xx<0 ||yy<0 ||xx>=n ||yy>=m) continue; if(map[xx][yy]=='*') continue; dfs(xx,yy); } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); while(scan.hasNext()){ n=scan.nextInt(); m=scan.nextInt(); if(n==0 && m==0) break; for(int i=0;i<n;i++){ map[i]=scan.next().toCharArray(); } cnt=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(map[i][j]=='@'){ dfs(i,j); cnt++; } System.out.println(cnt); } } }