HDU 1312 Red and Black DFS(深度优先搜索) 和 BFS（广度优先搜索）

Red and Black

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 6762 Accepted Submission(s): 4284

Problem Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

'.' - a black tile

'#' - a red tile

'@' - a man on a black tile(appears exactly once in a data set)

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output

45
59
6
13

方法一  DFS（深度优先搜素）

import java.io.*;
import java.util.*;
public class Main {
	int M=22,w,h,sx,sy;
	char ch[][];
	int fx[]={1,-1,0,0};
	int fy[]={0,0,1,-1};
	int number;
	boolean boo[][]=new boolean[100][100];
	public static void main(String[] args) {
		new Main().work();
	}
	void work(){
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		while(sc.hasNext()){
			w=sc.nextInt();
			h=sc.nextInt();
			if(h==0&&w==0)
				System.exit(0);
			ch=new char[h][w];
			for(int i=0;i<h;i++){
				String s=sc.next();
				ch[i]=s.toCharArray();
				Arrays.fill(boo[i], false);
			}
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					if(ch[i][j]=='@'){
						sx=i;
						sy=j;
					}
				}
			}
			number=1;
			boo[sx][sy]=true;
			DFS(sx,sy);
			System.out.println(number);
		}
	}
	void DFS(int sx,int sy){
		for(int i=0;i<4;i++){
			int px=sx+fx[i];
			int py=sy+fy[i];
			if(check(px,py)&&!boo[px][py]){
				number++;
				boo[px][py]=true;
				DFS(px,py);
			}
		}
	}
	boolean check(int px,int py){
		if(px<0||px>h-1||py<0||py>w-1||ch[px][py]!='.')
			return false;
		return true;
	}
}

方法二  BFS( 广度优先搜索)

import java.io.*;
import java.util.*;

public class Main {
	Queue<Node> que = new LinkedList<Node>();
	boolean boo[][] = new boolean[100][100];
	char ch[][];
	int w, h;
	int fx[] = { 1, -1, 0, 0 };
	int fy[] = { 0, 0, 1, -1 };
	int number;

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

	void work() {
		Scanner sc = new Scanner(new BufferedInputStream(System.in));
		while (sc.hasNext()) {
			w = sc.nextInt();
			h = sc.nextInt();
			if(h==0&&w==0)
				System.exit(0);
			ch = new char[h][w];
			for (int i = 0; i < h; i++) {
				String s = sc.next();
				ch[i] = s.toCharArray();
				Arrays.fill(boo[i], false);
			}
			Node node = new Node();
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (ch[i][j] == '@') {
						node.x = i;
						node.y = j;
						node.number = 1;
					}
				}
			}
			boo[node.x][node.y] = true;
			que.add(node);
			number = 1;
			BFS();
			System.out.println(number);

		}
	}

	void BFS() {
		while (!que.isEmpty()) {

			Node node = que.poll();
			for (int i = 0; i < 4; i++) {
				int px = node.x + fx[i];
				int py = node.y + fy[i];
				if (check(px, py) && !boo[px][py]) {
					number++;
					Node td = new Node();
					td.x = px;
					td.y = py;
					boo[px][py] = true;
					ch[px][py] = 'S';
					que.add(td);
				}
			}
		}
	}

	boolean check(int px, int py) {
		if (px < 0 || px > h - 1 || py < 0 || py > w - 1 || ch[px][py] != '.')
			return false;
		return true;
	}

	class Node {
		int x;
		int y;
		int number;

	}
}