杭電OJ-1312 Red and Black

Red and Black
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 26912    Accepted Submission(s): 16229
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
 
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1312
2つの方法があります.古典的な点はdfsです.@点から出発して、歩くことができる点ごとに検索してカウントします.同時に、アクセスしたことがあるようにして、次のステップでカウントを繰り返すことを防止します.コードは以下の通りです.

#include
using namespace std;
int n, m, px, py, ans;
char Map[30][30];
int vis[30][30], dir[8] = {0, 1, 0, -1, 1, 0, -1, 0};
void dfs(int x, int y) {
  for(int i = 0; i < 8; i += 2) {
    int nx = x + dir[i], ny = y + dir[i+1];
    if(nx > 0 && nx <= m && ny > 0 && ny <= n && Map[nx][ny] == '.' && !vis[nx][ny]) {
      ans++;
      vis[nx][ny] = 1;
      dfs(nx, ny);
    }
  }
}
int main() {
  while(~scanf("%d%d", &n, &m)) {
    if(n == 0 && m == 0) break;
    memset(Map, 0, sizeof(Map));
    memset(vis, 0, sizeof(vis));
    ans = 1;
    for(int i = 1; i <= m; i++) {
      getchar();
      for(int j =1; j <= n; j++) {
        scanf("%c", &Map[i][j]);
        if(Map[i][j] == '@') {
          px = i;
          py = j;
          Map[i][j] = '.';
        }
      }
    }
    vis[px][py] = 1;
    dfs(px, py);
    printf("%d
", ans);
  } 
  return 0;
}

もう1つの方法は、図上のすべての点を構造体で番号付けして番号を記録し、その点の値(文字)を記録することです.各点を遍歴し、ある点が上下左右4方向の点とマージできるかどうかを判断し、マージするには、小さい番号の点にマージしてルートノードとします.ここで注意したいのは、完全にマージするには、必ず2回、つまり2回、マージしなければなりません.最後に構造体を巡回し、点の番号が始点の番号(同じルートノードであることを示す)に等しい場合はカウントします.(これは非常に良く、典型的な連結ブロック内の点の数を統計するために使用される問題です)コードは以下の通りです.

#include
using namespace std;
int n, m, cnt, px, py, ans;
struct point {
  int num;//         ， 1  ,               
  char ch;
}p[450];
int find(int x) {
  if(x == p[x].num) return p[x].num;
  return p[x].num = find(p[x].num);
}
void join(int x, int y) {
  int fx = find(x), fy = find(y);
  if(fy < fx) p[fx].num = fy;//                
  if(fx < fy) p[fy].num = fx;
}
int main() {
  while(~scanf("%d%d", &n, &m)) {
    if(n == 0 && m == 0) break;
    memset(p, 0, sizeof(p));
    cnt = 1, ans = 0;
    for(int i = 1; i <= m; i++) {
      getchar();
      for(int j =1; j <= n; j++) {
        scanf("%c", &p[cnt].ch);
        p[cnt].num = cnt;//      ，             
        if(p[cnt].ch == '@') {
          px = i;
          py = j;
          p[cnt].ch = '.';//     .           
        }
        cnt++;
      }
    }
    int k = 1;
    for(int i = 1; i <= m; i++) {
      for(int j = 1; j <= n; j++) {
        if(p[k].ch == '.' && i-1 > 0 && p[k-n].ch == '.') join(k, k-n);//       . 
        if(p[k].ch == '.' && i+1 <= m && p[k+n].ch == '.') join(k, k+n);//       . 
        if(p[k].ch == '.' && j-1 > 0 && p[k-1].ch == '.') join(k, k-1);//       . 
        if(p[k].ch == '.' && j+1 <= n && p[k+1].ch == '.') join(k, k+1);//       . 
        k++;
      }
    } 
    k = 1;
    for(int i = 1; i <= m; i++) {//          
      for(int j = 1; j <= n; j++) {
        if(p[k].ch == '.' && i-1 > 0 && p[k-n].ch == '.') join(k, k-n);//       . 
        if(p[k].ch == '.' && i+1 <= m && p[k+n].ch == '.') join(k, k+n);//       . 
        if(p[k].ch == '.' && j-1 > 0 && p[k-1].ch == '.') join(k, k-1);//       . 
        if(p[k].ch == '.' && j+1 <= n && p[k+1].ch == '.') join(k, k+1);//       .
        k++; 
      }
    }
    for(int i = 1; i < cnt; i++)
      if(p[i].num == p[n*(px-1)+py].num) ans++;
    printf("%d
", ans);
  } 
  return 0;
}

JAvaコード(dfs):

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Mai {
	
	public static Scanner in = new Scanner(new BufferedInputStream(System.in));
	
	public static int n, m, px, py, ans;
	public static char[][] Map;
	public static int[][] vis; 
	public static int dir[] = {0, 1, 0, -1, 1, 0, -1, 0};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		while(true) {
			ans = 1;
			String s = in.nextLine();
			String[] ss = s.split(" ");
			n = Integer.parseInt(ss[0]);
			m = Integer.parseInt(ss[1]);
			if(n == 0 && m == 0) break;
			vis = new int[30][30];//  
			Map = new char[30][30];
			for(int i = 1; i <= m; i++) {
			      String str = in.nextLine();
			      for(int j = 1; j <= n; j++) {
			        Map[i][j] = str.charAt(j-1);
			        if(Map[i][j] == '@') {
			          px = i;
			          py = j;
			          Map[i][j] = '.';
			        }
			      }
			    }
			    vis[px][py] = 1;
			    dfs(px, py);
			    System.out.println(ans);
		}
	}

	public static void dfs(int x, int y) {
		for (int i = 0; i < 8; i += 2) {
			int nx = x + dir[i], ny = y + dir[i + 1];
			if (nx > 0 && nx <= m && ny > 0 && ny <= n && Map[nx][ny] == '.' && vis[nx][ny] == 0) {
				ans++;
				vis[nx][ny] = 1;
				dfs(nx, ny);
			}
		}
	}
}