# 51-迷宫（一）- java版dfs和bfs

### 数据范围

1 \le n, m \le 10

#### 样例输入1

3 4
S**.
..*.
***T

#### 样例输出1

no

#### 样例输入2

3 4
S**.
....
***T

#### 样例输出2

yes

bfs:  就是遍历周围的格子，能走的放入到一个Stack里面，然后放完，就一次去取，一层一层的取，注意要用一个 visit判断是否以前放入了，一旦重复放入那就会死循环。

import java.util.Scanner;
import java.util.Stack;

public class Main{
public static String mp[] = new String[11];
public static int visit[][] = new int[11][11];
public static int ans = 0;
public static int n, m;

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

n = cin.nextInt();
m = cin.nextInt();

for(int i = 0; i < n; i++) {
mp[i] = cin.next();
//			System.out.println(i + mp[i]);
}
//		System.out.println("-----");
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(mp[i].charAt(j) == ‘S‘) {
dfs(i,j);
break;
}
}
}
if(ans == 0) {
System.out.println("no");
}
else {
System.out.println("yes");
}
}

public static void dfs(int x0, int y0) {
node no = new node(x0, y0);
Stack<node> stack = new Stack<node>();
visit[x0][y0] = 1;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

while(!stack.empty()) {
node nd = stack.pop();
for(int i = 0; i < 4; i++) {
int x = nd.x + dx[i];
int y = nd.y + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m &&
visit[x][y] == 0 && mp[x].charAt(y) != ‘*‘) {
if(mp[x].charAt(y) == ‘T‘) {
ans = 1;
return ;
}
else {
node temp = new node(x, y);
visit[x][y] = 1;
}
}
}

}

}

}

class node{
int x, y;
node(){

}
node(int x0, int y0){
this.x = x0;
this.y = y0;
}
}



dfs:

import java.util.Scanner;

public class Main1{
public static String mp[] = new String[11];
public static int[][] visit = new int[11][11];
public static int n, m, ans;
public static int dx[] = {0, 0, 1, -1};
public static int dy[] = {1, -1, 0, 0};

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

n = cin.nextInt();
m = cin.nextInt();

for(int i = 0; i < n; i++) {
mp[i] = cin.next();
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(mp[i].charAt(j) == ‘S‘) {
visit[i][j] = 1;
dfs(i, j);
break;
}
}
}
if(ans == 1) {
System.out.println("yes");
}
else {
System.out.println("no");
}
}
public static void dfs(int x0, int y0) {
if(mp[x0].charAt(y0) == ‘T‘) {
ans = 1;
return ;
}
for(int i = 0; i < 4; i++) {
int x = x0 + dx[i];
int y = y0 + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m
&& visit[x][y] == 0 && mp[x].charAt(y) != ‘*‘) {
visit[x][y] = 1;
dfs(x, y);
visit[x][y] = 0;
}
}
}

}


51-迷宫（一）- java版dfs和bfs

(0)
(0)

0条