代码
package test_201312;
import java.util.Scanner;
/*
* 201312-5
试题名称： I’m stuck!
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
问题描述
给定一个R行C列的地图，地图的每一个方格可能是'#', '+', '-', '|', '.', 'S', 'T'七个字符中的一个，分别表示如下意思：
'#': 任何时候玩家都不能移动到此方格；
'+': 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'-': 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非'#'方格移动一格；
'|': 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非'#'方格移动一格；
'.': 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为'#'，则玩家不能再移动；
'S': 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'T': 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格。
此外，玩家不能移动出地图。
请找出满足下面两个性质的方格个数：
1. 玩家可以从初始位置移动到此方格；
2. 玩家不可以从此方格移动到目标位置。
输入格式
输入的第一行包括两个整数R 和C，分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。
接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个'S'和一个'T'。
输出格式
如果玩家在初始位置就已经不能到达终点了，就输出“I'm stuck!”（不含双引号）。否则的话，输出满足性质的方格的个数。
样例输入
5 5
--+-+
..|#.
..|##
S-+-T
####.
样例输出
2
样例说明
如果把满足性质的方格在地图上用'X'标记出来的话，地图如下所示：
--+-+
..|#X
..|##
S-+-T
####X
*/
public class Main5 {
// 代表输入的字符
static char map[][];
// 偏移量，上、右、下、左
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
// 从起点能够到达的点的标识
static boolean[][] vis1;
// 能够到达终点的点的标识
static boolean[][] vis2;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int R = input.nextInt();
int C = input.nextInt();
map = new char[R][C];
vis1 = new boolean[R][C];
vis2 = new boolean[R][C];
int S_i = 0, S_j = 0, T_i = 0, T_j = 0;
for (int i = 0; i < R; i++) {
String strline = input.next();// 获取一行字符串
for (int j = 0; j < C; j++) {
map[i][j] = strline.charAt(j);// 获取对应的字符,并获得S和T的位置
if (map[i][j] == 'S') {
S_i = i;
S_j = j;
} else if (map[i][j] == 'T') {
T_i = i;
T_j = j;
}
}
}
input.close();
dfs1(S_i, S_j);
dfs2(T_i, T_j);
// 如果起点无法到终点
if (!vis1[T_i][T_j]) {
System.out.println("I'm stuck!");
} else {
// 统计能够从起点到该点且从该点也可以到终点的格子数量
int res = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (vis1[i][j] && !vis2[i][j]) {
res++;
}
}
}
System.out.println(res);
}
}
// 标记起点能够到达的节点
private static void dfs1(int x, int y) {
vis1[x][y] = true;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r < 0 || c < 0 || r >= map.length || c >= map[0].length || map[r][c] == '#' || vis1[r][c]) {
continue;
}
// 判断从(x,y)是否能够到达(r,c)，若不能到达，则递归结束
if (check(x, y, i)) {
dfs1(r, c);
}
}
}
/**
* 检测从(x,y)是否能够移动到(r,c),(r,c)由i索引的dx、dy定位
*
* @param x
* @param y
* @param i
* @return
*/
private static boolean check(int x, int y, int i) {
char c = map[x][y];
if (c == 'S' || c == 'T' || c == '+') {
return true;
} else if (c == '|' && (i == 0 || i == 2)) {
return true;
} else if (c == '-' && (i == 1 || i == 3)) {
return true;
} else if (c == '.' && i == 2) {
return true;
} else {
return false;
}
}
/**
* 标记终点能够到达的节点
*
* @param x
* @param y
*/
private static void dfs2(int x, int y) {
vis2[x][y] = true;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
// 边界条件,以及判断是否已经访问过了
if (r < 0 || c < 0 || r >= map.length || c >= map[0].length || map[r][c] == '#' || vis2[r][c]) {
continue;
}
// 检测能否通过(r,c)到达(x,y)，若不能到达，则递归结束
if (check(r, c, i ^ 2)) {// 这里通过异或运算，得到的顺序和上面刚好相反，即上面是按照上、右、下、左顺序搜索，而这里就是下、左、上、右判断！
dfs2(r, c);
}
}
}
}
代码分析
先初始化map二维数组，并得到S和T的位置。然后dfs1深搜从初始位置可以到达的全部方格；dfs2深搜可以移动到目标位置的全部方格。最后根据规则输出。
dfs1尝试上下左右四个方向，探索是否有移动可能。
1.先判断目标位置是否可以到达
if (r < 0 || c < 0 || r >= map.length || c >= map[0].length || map[r][c] == '#' || vis1[r][c]) {
continue;
}
2.判断当前位置(x,y)是否可以进行i移动
if (check(x, y, i)) {
dfs1(r, c);
}
dfs2和dfs1功能相似。
dfs1考察从当前节点是否可以向四个方向移动，dfs2考察从四周是否可以到达当前节点。
dfs2
我们通过
int r = x + dx[i];
int c = y + dy[i];
获得四周节点，而check时需要检查，从四周节点是否可以到达当前节点，故第三个参数检查相反的移动方向是否可以。
if (check(r, c, i ^ 2)) {// 这里通过异或运算，得到的顺序和上面刚好相反，即上面是按照上、右、下、左顺序搜索，而这里就是下、左、上、右判断！
dfs2(r, c);
}
本题只是使用了和图深度遍历同样的思想，并不是考察图结构的深度遍历。只是深度遍历二维数组。
一个基本模板如下：
import java.util.Random;
public class TwoArrDfs {
static Random random = new Random();
private static void print(int[][] arrtwo) {
for(int i = 0; i < arrtwo.length; i++){
for(int j = 0; j < arrtwo[i].length; j++){
System.out.print(arrtwo[i][j]+" ");
}
System.out.println();
}
}
private static void dfs(int[][] arrtwo, int i, int j) {
arrtwo[i][j] = random.nextInt(20)+1;
//是否可以向上走
if(i > 0 && arrtwo[i-1][j]==0){
dfs(arrtwo, i-1, j);
}
//是否可以向下走
if(i < arrtwo.length - 1 && arrtwo[i+1][j]==0){
dfs(arrtwo, i+1, j);
}
//是否可以向左走
if(j > 0 && arrtwo[i][j-1]==0){
dfs(arrtwo, i, j-1);
}
//是否可以向右走
if(j < arrtwo[0].length - 1 && arrtwo[i][j+1]==0){
dfs(arrtwo, i, j+1);
}
}
public static void main(String[] args) {
int[][] arr = new int[4][5];
dfs(arr,0,0);
print(arr);
}
}
![[Java安全入门]三.URLDNS链](https://img-blog.csdnimg.cn/direct/4dd079fb991e41e3becc80c4bd5fb5dc.png)
