题目描述
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
样例
输入样例:
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例:
45
算法1
(DFS) $O(nm)$
java 代码
import java.io.*;
import java.util.*;
class Main{
static final int N = 25;
static int n,m,res;
static String[] map = new String[N];
static boolean[][] st=new boolean[N][N];
static int[][] ne=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
static void dfs(int x,int y){
st[y][x]=true;
res++;
for(int i=0;i<=3;++i){
int xt=x+ne[i][0],yt=y+ne[i][1];
if(xt>=0 && xt<n && yt>=0 && yt<m && !st[yt][xt] && map[yt].charAt(xt) == '.'){
dfs(xt,yt);
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
while(true){
String[] in = bf.readLine().split(" ");
n=Integer.parseInt(in[0]); m=Integer.parseInt(in[1]);
if(n==0 && m==0) break;
int x=0, y=0;
for(int i=0;i<m;++i){
map[i] = bf.readLine();
int t=map[i].indexOf('@');
if(t != -1){
x=t;
y=i;
}
}
res=0;
for(int i=0;i<m;++i) Arrays.fill(st[i],false);
dfs(x,y);
System.out.println(res);
}
bf.close();
}
}