POJ 1979 Red and Black

##题目链接

##解决方法

这道题容易想到的是可以用深度优先搜索解决。

深度优先搜索(Depth-First-Search)：从最开始的状态出发，遍历所有可以到达的状态，直到无法再深入时，返回上个状态，去访问该“上个状态”可以到达的别的状态，重复这个过程直到遍历完所有状态。

具体到此题，从起点开始，从点的上下左右4个方向分别访问。访问过的'.'改为'#'，用以标记该'.'已经访问过，避免重复计算。

举个例子，假设输入如下：

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#. 

其中，起点坐标为(1,7)，从起点为中心开始遍历4个方向，假设先访问点(0,7)，读取该点发现内容是'#'，不能走。接着访问点(2,7)，读取该点发现内容是'.'，可以走，所以计数器加1，并把该点内容改为'#'，以防止被重复计数。再以(2,7)为中心，向4个方向遍历（注意：此时(1,7)四个方向的点并没有访问完）。重复这个过程，直到访问到最后一个点的四个方向，发现已经遍历到最大深度，此时程序倒回访问上一个点的下一个方向。后面的过程以此类推。

##实现代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Test().fun();
    }
}

class Test{
    private int w,h;
    private char[][] tiles;
    private int sx,sy;       // start point
    private int result = 0;  // 计数

    //4个方向的移动向量
    private final int[] dx = { 1, 0, -1, 0 };
    private final int[] dy = { 0, 1, 0, -1 };

    public void fun(){
        Scanner cin = new Scanner(System.in);
        w = cin.nextInt();   //with
        h = cin.nextInt();   //height  
    
        while(true){
            if(w==0 || h==0){
                break;
            }
        
            tiles = new char[h][w];

            //get input
            String temp;
            for(int i=0; i<h; i++){
                temp = cin.next();
                for(int j=0; j<w; j++){
                    tiles[i][j] = temp.charAt(j);
                    if( tiles[i][j]=='@' ){   //get start point
                        sx = i;
                        sy = j;
                    }  
                }
            }
        
            dfs(sx,sy);
        
            System.out.println(result);
        
            result = 0;
        
            w = cin.nextInt();   //with
            h = cin.nextInt();   //height  
        }

        cin.close();
    }

    //深度优先遍历
    public void dfs(int x,int y){
        tiles[x][y] = '#';

        result++;

        int tmpx,tmpy;
        for(int i=0; i<4; i++){
            tmpx = x + dx[i];
            tmpy = y + dy[i];
            if( tmpx>=0 && tmpx<h && tmpy>=0 && tmpy<w
                    && tiles[tmpx][tmpy]=='.' ){
                dfs(tmpx,tmpy);
            }
        }

    }
}

行云流水's Bolg

about

POJ 1979 Red and Black