题目描述

dfs bfs都可以实现，重点记录一下dfs的思路
1.本题注意的地方，有多组测试数据，需要每次初始化字符数组和判重数组
2.res作为全局变量，统计每一次的瓷砖个数，但是进行下一组测试数据的视乎，也需要将res初始化

dfs代码

package dfs;

import java.util.Arrays;
import java.util.Scanner;

public class 红与黑 {

    static int N=30,n,m,stx,sty,res=1;
    static int[] dx = new int[] {-1,0,1,0};
    static int[] dy = new int[] {0,1,0,-1};
    static boolean  st[][]=new boolean [N][N];
    static String g[]=new String [N];

    public static  void   dfs(int x,int y) {

        st[x][y]=true;
        for(int i=0;i<4;i++) {
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=n || b>=m || a<0 || b<0) continue;
            if(g[a].charAt(b)!='.') continue;
            if(st[a][b]) continue;
            res++;
            dfs(a, b);
        }

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
    Scanner scanner =new Scanner(System.in);
    while(true) {
        m=scanner.nextInt();
        n=scanner.nextInt();
        if(m==0 && n==0) break;
        scanner.nextLine();
        for(int i=0;i<n;i++) {
            g[i]=scanner.nextLine();
            Arrays.fill(st[i], false);
            for(int j=0;j<m;j++) {
                if(g[i].charAt(j)=='@') {
                    stx=i;
                    sty=j;
                }
            }
        }
        dfs(stx, sty);
        System.out.println(res);
    }


    }

}

bfs代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Br{
    int x;
    int y;
    public Br(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

}
public class Main {

    /**
     * @param args
     */
    public static int w,h,N=30,cnt=0;
    public static String g[]=new String[N];
    public static int stx,sty;
    public static boolean st[][] =new boolean[N][N];
    public static int dx[]={0,0,1,-1};
    public static int dy[]={1,-1,0,0};


    public static int bfs(int x, int y){



        cnt=0;
        Queue<Br> queue = new LinkedList<Br>();
        queue.add(new Br(x, y));
        cnt++;
        st[x][y]=true;

        while(!queue.isEmpty()){
            Br tBr=queue.poll();
            //cnt++;
            int xx=tBr.x;
            int yy=tBr.y;
            for(int i=0;i<4;i++){
                int a=xx+dx[i];
                int b=yy+dy[i];
                if(a<0 || b<0 || a>=h || b>=w) continue;
                if(st[a][b]) continue;
                if(g[a].charAt(b)=='#') continue;

                queue.add(new Br(a, b));
                st[a][b]=true;
                cnt++;

            }
        }
        return cnt;
    }


    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
     BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
     while(true){
         for(int i=0;i<N;i++) Arrays.fill(st[i], false);
        Arrays.fill(g, null);
         String p[]=bufferedReader.readLine().split(" ");
         w=Integer.parseInt(p[0]);
         h=Integer.parseInt(p[1]);
         if(w==0 && h==0) break;
         for(int i=0;i<h;i++){
             g[i]=bufferedReader.readLine();
             for(int j=0;j<w;j++){
                 if(g[i].charAt(j)=='@'){
                     stx=i;
                     sty=j;
                 }
             }

         }
        System.out.println(bfs(stx, sty));
     }



    }

}