【题目描述】
DFS
res统计 该点能到达的所有点
import java.util.Scanner;
class Main{
static int N = 25;
static char [][] g = new char[N][N];
static int dir[][] ={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static int dfs(int x, int y, int m, int n){
int res = 1;
//标记为访问过
g[x][y] = '#';
for(int i = 0; i < 4; i++){
int a = x + dir[i][0], b = y + dir[i][1];
//越界 使用continue
if(a < 0 || a >= m || b < 0 || b >= n) continue;
//访问过
if(g[a][b] == '#') continue;
res += dfs(a, b, m, n);
}
return res;
}
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
while(true){
int n = reader.nextInt(), m = reader.nextInt();
if( n == 0 && m == 0) break;
for(int i = 0; i < m; i ++)
g[i] = reader.next().toCharArray();
int sx = 0, sy = 0;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
if(g[i][j] == '@'){
sx = i;
sy = j;
}
System.out.println(dfs(sx, sy, m, n));
}
}
}
或标记可写成如下：
import java.util.Scanner;
class Main{
static int N = 25;
static char [][] g = new char[N][N];
static int dir[][] ={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static int dfs(int x, int y, int m, int n){
int res = 1;
//标记为访问过
for(int i = 0; i < 4; i++){
int a = x + dir[i][0], b = y + dir[i][1];
//越界 使用continue
if(a < 0 || a >= m || b < 0 || b >= n) continue;
//访问过
if(g[a][b] == '#') continue;
//加入时 即标记为访问过
g[a][b] = '#';
res += dfs(a, b, m, n);
}
return res;
}
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
while(true){
int n = reader.nextInt(), m = reader.nextInt();
if( n == 0 && m == 0) break;
for(int i = 0; i < m; i ++)
g[i] = reader.next().toCharArray();
int sx = 0, sy = 0;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
if(g[i][j] == '@'){
sx = i;
sy = j;
}
g[sx][sy] = '#';
System.out.println(dfs(sx, sy, m, n));
}
}
}
BFS
import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
class Node{
int x, y;
public Node(int xx, int yy){
x = xx;
y = yy;
}
}
class Main{
static int N = 25;
static char [][] g = new char[N][N];
static int dir[][] ={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
while(true){
int n = reader.nextInt(), m = reader.nextInt();
if( n == 0 && m == 0) break;
for(int i = 0; i < m; i ++)
g[i] = reader.next().toCharArray();
int sx = 0, sy = 0;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
if(g[i][j] == '@'){
sx = i;
sy = j;
}
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(sx, sy));
int cnt = 0;
while(!q.isEmpty()){
Node h = q.poll();
int x = h.x, y = h.y;
g[x][y] = '#';
cnt ++;
for(int i = 0; i < 4; i ++){//保证每个未被访问过的且可以到达的点只入队一次
int a = x +dir[i][0], b = y + dir[i][1];
if(a < 0 || a >= m || b < 0 || b >= n || g[a][b] == '#') continue;
//此处不标记，会重复入队列，有陷入死循环的可能
g[a][b] = '#';
q.offer(new Node(a, b));
}
}
System.out.println(cnt);
}
}
}
或将标记写成如下：
import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
class Node{
int x, y;
public Node(int xx, int yy){
x = xx;
y = yy;
}
}
class Main{
static int N = 25;
static char [][] g = new char[N][N];
static int dir[][] ={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static void main(String args[]){
Scanner reader = new Scanner(System.in);
while(true){
int n = reader.nextInt(), m = reader.nextInt();
if( n == 0 && m == 0) break;
for(int i = 0; i < m; i ++)
g[i] = reader.next().toCharArray();
int sx = 0, sy = 0;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
if(g[i][j] == '@'){
sx = i;
sy = j;
}
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(sx, sy));
g[sx][sy] = '#';
int cnt = 0;
while(!q.isEmpty()){
Node h = q.poll();
int x = h.x, y = h.y;
cnt ++;
for(int i = 0; i < 4; i ++){//保证每个未被访问过的且可以到达的点只入队一次
int a = x +dir[i][0], b = y + dir[i][1];
if(a < 0 || a >= m || b < 0 || b >= n || g[a][b] == '#') continue;
//此处不标记，会重复入队列，有陷入死循环的可能
g[a][b] = '#';
q.offer(new Node(a, b));
}
}
System.out.println(cnt);
}
}
}
如果写成如下，同一个节点会重复多次加入队列中。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
*/
/**
* @author JohnnyLin
* @version Creation Time：2021年1月14日 下午10:01:17
*
*/
class Node{
int x, y;
public Node(int xx, int yy) {
x = xx;
y = yy;
}
}
public class Main {
//顺时针方向
static int dir[][] = {{-1,0},{0,1},{1,0},{0,-1}};
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt(); //列
int m = reader.nextInt(); //行
while(m != 0&& n != 0) {
char map[][] = new char [m][n];
boolean vis[][] = new boolean[m][n];
int sx = 0, sy = 0;
for(int i = 0; i < m; i++) {
String s = reader.next();
for(int j = 0; j < n; j++) {
map [i][j] = s.charAt(j);
if(map [i][j] == '@') {
sx = i;
sy = j;
}
}
}
int cnt = 0;
Queue<Node> q = new LinkedList<Node>();
//标记为已经访问过
q.offer(new Node(sx, sy));
while(q.size() != 0) {
Node node = q.poll();;
cnt++;
int x = node.x, y = node.y;
map[x][y] = '#';
//往四个邻接方格扩展
for(int i = 0; i < 4; i++) {
int a = x + dir[i][0], b = y +dir[i][1];
//越界或者访问过或者为红砖
if(a < 0 || a >= m || b < 0 || b >=n || map[a][b] == '#')continue;
//应该在此处标记访问过
q.offer(new Node(a, b));
}
}
System.out.println(cnt);
m = reader.nextInt();
n = reader.nextInt();
}
}
}
