原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目名称：骨的诱惑
问题描述：
迷宫是一个矩形，大小为N×M。迷宫中有一扇门。
刚开始时，门是关闭的，它将在第T秒打开一小段时间（少于1秒）。
因此，小狗必须在第T秒精确到达门。每秒钟，他可以将一个块移动到上，下，左和右相邻的块之一。
一旦他进入一个街区，该街区的地面将开始下沉并在下一秒消失。他不能在一个街区停留超过一秒钟，也不能搬到一个拜访的街区。
输入项：
输入包含多个测试用例。
每个测试用例的第一行包含三个整数N，M和T（1 <N，M <7； 0 <T <50），分别表示迷宫的大小和门打开的时间。
接下来的N行给出迷宫布局，每行包含M个字符。
'X'：小狗无法进入的墙块；
'S'：小狗的起点；
'D'：门；或
'.'：空白块。
然后又是一些数字和地图，直到0 0 0表示结束
输出项：
是或者否
解题技巧：图的广度优先遍历搜索算法测试用例：
3 4 5
S...
.X.X
...D
4 4 8
.X.X
..S.
....
DX.X
4 4 5
S.X.
..X.
..XD
....
0 0 0
输出结果：
是
是
否
java代码:
public class Hdu1010 {final static String yes = "是", no = "否";static int si, sj, di, dj;//起点和终点的坐标static int wall = 0;//墙的数量static int n, m;static int go[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//往上下左右走横纵左边变化static String map[][];public static void main(String[] args) {List<Hdu1010DataStructure> hdu1010DataStructures = read();//读取输入的内容//进行处理，输出最终结果for (int i = 0; i < hdu1010DataStructures.size(); i++) {System.out.println(count(hdu1010DataStructures.get(i)));}}//对图进行处理static String count(Hdu1010DataStructure hDataStructure) {wall = 0;map = hDataStructure.getMap();n = hDataStructure.getN();m = hDataStructure.getM();int t = hDataStructure.getT();//找到起点和终点for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i][j].equals("S")) {si = i;sj = j;} else if (map[i][j].equals("D")) {di = i;dj = j;} else if (map[i][j].equals("X")) {++wall;}}}//减枝的情况，如果表格的大小小于墙加时间，那么不可能完成if (n * m <= wall + t) return no;//把起点设置成为墙壁，然后走路map[si][sj] = "X";return dfs(si, sj, di, dj, t);}//广度优先遍历static String dfs(int si, int sj, int di, int dj, int t) {if (si == di && sj == dj && t == 0) return yes;//成功if (si != di && sj != dj && t == 0) return no;int temp = t - Math.abs(si - di) - Math.abs(sj - dj);//剩余步数能不能在无墙壁情况下到达if (temp < 0 || temp % 2 == 1) {//temp是奇数或者小于0表示无法到达（是偶数我们可以浪费步数）return no;}//四个方向的遍历for (int i = 0; i < 4; i++) {if (si == 0 && i == 0) continue;//第一行时不能向上if (si == n - 1 && i == 1) continue;//最后一行不能向下if (sj == 0 && i == 2) continue;//第一列时不能向左if (sj == m - 1 && i == 3) continue;//最后一列不能向右if (!map[si + go[i][0]][sj + go[i][1]].equals("X")) {//不是墙//变成墙,往下走时间减1map[si + go[i][0]][sj + go[i][1]] = "X";String result = dfs(si + go[i][0], sj + go[i][1], di, dj, t - 1);if (result.equals("是")) return yes;//递归中找到出口map[si + go[i][0]][sj + go[i][1]] = ".";//回退}}return no;//四个方向都不行 就返回no}//读取输入的内容 0 0 0表示结束(第一个为0表示结束)static List<Hdu1010DataStructure> read() {//输入一个字符串Scanner scanner = new Scanner(System.in);String NMT[] = scanner.nextLine().split(" ");List<Hdu1010DataStructure> hdu1010DataStructureList = new ArrayList<Hdu1010DataStructure>();while (!NMT[0].equals("0")) {Hdu1010DataStructure hdu1010DataStructure = new Hdu1010DataStructure();hdu1010DataStructure.setN(Integer.parseInt(NMT[0]));hdu1010DataStructure.setM(Integer.parseInt(NMT[1]));hdu1010DataStructure.setT(Integer.parseInt(NMT[2]));String map[][] = new String[Integer.parseInt(NMT[0])][Integer.parseInt(NMT[1])];for (int i = 0; i < Integer.parseInt(NMT[0]); ++i) {//行String stringRow = scanner.nextLine();for (int j = 0; j < Integer.parseInt(NMT[1]); j++) {//列map[i][j] = String.valueOf(stringRow.charAt(j));}}hdu1010DataStructure.setMap(map);//得到本次输入图hdu1010DataStructureList.add(hdu1010DataStructure);NMT = scanner.nextLine().split(" ");}return hdu1010DataStructureList;}
}
所对应的数据结构（Java对象）
import java.util.Arrays;
public class Hdu1010DataStructure {private int n;private int m;private int t;private String map[][];@Overridepublic String toString() {return "Hdu1010class{" +"n=" + n +", m=" + m +", t=" + t +", map=" + Arrays.toString(map) +'}';}public int getN() {return n;}public void setN(int n) {this.n = n;}public int getM() {return m;}public void setM(int m) {this.m = m;}public int getT() {return t;}public void setT(int t) {this.t = t;}public String[][] getMap() {return map;}public void setMap(String[][] map) {this.map = map;}
}