深度优先搜索算法-DepthFirstSearch(DFS)

短命女 2024-04-06 10:27 79阅读 0赞

package com.xch4.deep;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main1 {
    
    	//清除水洼问题：DFS（深搜）
    	public static int f1(char[][] table) {
    		int num=0;//水洼数目
    		for (int i = 0; i < table.length; i++) {
    			for (int j = 0; j < table[0].length; j++) {
    				if(table[i][j]=='w') {//找到水洼，清除水洼
    					dfs(table, i, j);
    					num++;
    				}
    			}
    		}
    		return num;
    	}
    	public static void dfs(char[][] table,int x,int y) {
    		table[x][y]='.';//标记
    		for (int i = x-1; i <=x+1; i++) {
    			for (int j = y-1; j <=y+1; j++) {
    				if(i>=0&&i<table.length&&j>=0&&j<table[0].length&&!(i==x&&j==y)){//不越界且不为自己
    					if(table[i][j]=='w') {
    						dfs(table, i, j);
    					}
    //					System.out.println(i+" "+j);//测试
    				}
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt(),m=sc.nextInt();//n行m列
    		char[][] table=new char[n][m];
    		for (int i = 0; i < table.length; i++) {
    			table[i]=sc.next().toCharArray();
    		}
    		System.out.println(f1(table));
    //		//测试用例
    //		10 12
    //		w........ww.
    //		.www.....www
    //		....ww...ww.
    //		.........ww.
    //		.........w..
    //		..w......w..
    //		.w.w.....ww.
    //		w.w.w.....w.
    //		.w.w......w.
    //		..w.......w.
    		
    //		//测试
    //		for (char[] cs : table) {
    //			System.out.println(Arrays.toString(cs));
    //		}
    //		dfs(table,1,1);
    		
    	}
    
    }