AcWing 1113 -java. 红与黑
原题链接
简单
作者:
神人
,
2021-01-12 20:53:12
,
所有人可见
,
阅读 187
dfs
import java.io.*;
public class AC1113 {
static int n;
static int m;
static char re[][] = new char[30][30];
static int[] dx = {-1, 0, 1, 0};
static int dy[] = {0, 1, 0, -1};
public static int dfs(int x, int y) {
re[x][y] = '@';
int ret = 1;
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a >= 0 && a < m && b >= 0 && b < n && re[a][b] == '.')
ret += dfs(a, b);
}
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int x = 0, y = 0;
while (true) {
String[] s = reader.readLine().split(" ");
int k = Integer.parseInt(s[1]);
int o = Integer.parseInt(s[0]);
if (k == 0 && o == 0) {
break;
}
m = k;
n = o;
for (int i = 0; i < k; i++) {
String str = reader.readLine();
for (int j = 0; j < o; j++) {
re[i][j] = str.charAt(j);
if (re[i][j] == '@') {
x = i;
y = j;
}
}
}
System.out.println(dfs(x, y));
}
}
}
//bfs
public static int bfs(int x ,int y){
int ret =0;
Queue<int []> q = new LinkedList<>();
q.offer(new int[]{x,y});
re[x][y] = '#';
while(!q.isEmpty()){
int[] peek = q.peek();
q.poll();
ret++;
for(int i = 0;i<4;i++){
int a = peek[0]+dx[i];
int b = peek[1]+dy[i];
if (a >= 0 && a < m && b >= 0 && b < n && re[a][b] == '.') {
re[a][b] = '#';
q.offer(new int[]{a,b});
}
}
}
return ret;
}