oildeposits.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.Scanner;


/**
 * ID:1562
 * DFS
 * @author yhm
 *
 */
public class OilDeposits {

	static int R;
	static int C;
	static boolean[][] grid;
	static boolean[][] M;
	static int result;
	
	static int[][] d={{1,0},{1,1},{1,-1},{0,-1},{0,1},{-1,0},{-1,1},{-1,-1}};
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			R = cin.nextInt();
			C = cin.nextInt();
			if(R==0 || C==0){
				break;
			}
			
			grid = new boolean[R][C];
			M = new boolean[R][C];
			result = 0;
			for(int i=0;i<R;i++){
				String str = cin.next();
				for(int j=0;j<C;j++){
					char ch = str.charAt(j);
					grid[i][j] = (ch=='@'?true:false); 
					M[i][j] = false;
				}
			}
			
			for(int i=0;i<R;i++){
				for(int j=0;j<C;j++){
					if(grid[i][j] && !M[i][j]){
						result++;
						DFS(i,j);
					}
				}
			}
			System.out.println(result);
			
		}

	}
	
	static boolean overflow(int r, int c){
		return (r<0 || c<0 || r>=R || c>=C);
	}
	
	static void DFS(int r, int c){
		M[r][c] = true;

		

		for(int i=0;i<8;i++){
			int newR = r + d[i][0];
			int newC = c + d[i][1];
			
			if(!overflow(newR, newC)){
				if(!M[newR][newC] && grid[newR][newC]){
					DFS(newR, newC);
				}
			}
			
		}

	}

}