-
import java.io.BufferedInputStream;
-
import java.util.Scanner;
-
-
import com.sun.org.apache.regexp.internal.recompile;
-
-
public class Main {
-
-
static int row;
-
static int col;
-
static int step;
-
static char maze[][] = new char[20][20];
-
static boolean isPosWalked[][] = new boolean[20][20];
-
static boolean isSuccess;
-
-
public static boolean dfs(char maze[][], int y, int x, int currentStep) {
-
if (maze[y][x] == ‘D‘ && currentStep == step) {
-
isSuccess = true;
-
} else if (maze[y][x] == ‘D‘ && currentStep != step) {
-
return false;
-
}
-
isPosWalked[y][x] = true;
-
-
if (x < col - 1 && maze[y][x + 1] != ‘X‘ && !isPosWalked[y][x + 1]) {
-
dfs(maze, y, x + 1, currentStep + 1);
-
}
-
-
if (y < row - 1 && maze[y + 1][x] != ‘X‘ && !isPosWalked[y + 1][x]) {
-
dfs(maze, y + 1, x, currentStep + 1);
-
}
-
-
if (x > 0 && maze[y][x - 1] != ‘X‘ && !isPosWalked[y][x - 1]) {
-
dfs(maze, y, x - 1, currentStep + 1);
-
}
-
-
if (y > 0 && maze[y - 1][x] != ‘X‘ && !isPosWalked[y - 1][x]) {
-
dfs(maze, y - 1, x, currentStep + 1);
-
}
-
isPosWalked[y][x] = false;
-
return false;
-
}
-
-
public static void print(char maze[][], int y, int x) {
-
for (int i = 0; i < y; i++) {
-
for (int j = 0; j < x; j++) {
-
System.out.print(maze[i][j]);
-
}
-
System.out.println();
-
}
-
}
-
-
public static void main(String[] args) {
-
Scanner sc = new Scanner(new BufferedInputStream(System.in));
-
row = sc.nextInt();
-
col = sc.nextInt();
-
step = sc.nextInt();
-
int startY = 0, startX = 0;
-
while (row != 0 || col != 0 || step != 0) {
-
for (int i = 0; i < row; i++) {
-
String tmp = sc.next();
-
for (int j = 0; j < col; j++) {
-
maze[i][j] = tmp.charAt(j);
-
if (maze[i][j] == ‘S‘) {
-
startY = i;
-
startX = j;
-
}
-
}
-
}
-
isSuccess = false;
-
for (int i = 0; i < 20; i++) {
-
for (int j = 0; j < 20; j++) {
-
isPosWalked[i][j] = false;
-
}
-
}
-
dfs(maze, startY, startX, 0);
-
if (isSuccess) {
-
System.out.println("YES");
-
} else {
-
System.out.println("NO");
-
}
-
-
-
row = sc.nextInt();
-
col = sc.nextInt();
-
step = sc.nextInt();
-
}
-
}
-
}
最近写的题目多用到dfs，一年前用C没写出来一直WA，今天看到hdu的Discussion有同学提供了很多测试数据，逐个把答案不同的调试一下终于AC
有这么几个要点：
1.
2 2 3
SD
..
这样的testcase也是要输出YES的，转了一个圈什么的，所以首次到达Destination也要判断一下是否和Required-Step完全符合
2.其实也是比较基础的，返回到upper recrusion的时候要注意将各种值回归进入时的状态
[JAVA][HDU 1010][Tempter of the Bone]
原文：http://blog.csdn.net/szhielelp/article/details/41511203
