背景描述
ztw同志負責探測地下石油儲藏.ztw現在在一塊矩形區域探測石油.他通過專業設備，來分析每個小塊中是否蘊藏石油.如果這些蘊藏石油的小方格相鄰(橫向相鄰，縱向相鄰，還有對角相鄰)，那么它們被認為是同一油藏的一部分.在這塊矩形區域，可能有很多油藏.你的任務是確定有多少不同的油藏.
輸入
輸入可能有多個矩形區域(即可能有多組測驗)，每個矩形區域的起始行包含m和n，表示行和列的數量，1<=n，m<=100，如果m=0表示輸入的結束，接下來是n行，每行m個字符.每個字符對應一個小方格，并且要么是‘*’、代表沒有油，要么是‘@’，表示有油.(注意多組資料，必要的陣列要及時清空~)
輸出
對于每一個矩形區域，輸出油藏的數量.兩個小方格是相鄰的，當且僅當他們水平或者垂直或者對角線相鄰(即8個方向)，
示例輸入
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0示例輸出
0 1 2 2 代碼：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); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98368.html
標籤：其他