题目链接：https://vjudge.net/problem/POJ-3009
转载于：https://www.cnblogs.com/Ash-ly/p/5728439.html
题目大意:
要求把一个冰壶从起点“2”用最少的步数移动到终点“3”，其中0为移动区域，1为石头区域，冰壶一旦想着某个方向运动就不会停止，也不会改变方向（想想冰壶在冰上滑动），除非冰壶撞到石头1 或者 到达终点 3
需要注意的是：
冰壶撞到石头后，冰壶会停在石头前面，此时（静止状态）才允许改变冰壶的运动方向，而该块石头会破裂，石头所在的区域由1变为0. 也就是说，冰壶撞到石头后，并不会取代石头的位置。
终点是一个摩擦力很大的区域，冰壶若到达终点3，就会停止在终点的位置不再移动。并且，如果步数>10，则直接算失败，这条dfs搜索路径直接舍弃。
解题分析：
此题主要注意的是冰壶向某一个方向前进的时候，如果没有遇到障碍物或者是终点，则继续向该方向不断前进，将这一点转换为代码，其它的就与普通的dfs类似。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = ;
int map[MAXN + ][MAXN + ];
int stepX[] = { -, , , };//四个方向：上、下、左、右
int stepY[] = { , , -, };
int ans;//最短步数
int w, h;//w 为宽度(y) ，h为高度(x)，注意下
int stX, stY, edX, edY;//开始时“2”的位置和“3”的位置坐标 int check(int x, int y) {//返回 非2 代表可以往这个方向走 返回 非1 代表会停下来
if (map[x][y] == || map[x][y] == ) return ;
else if (map[x][y] == - || map[x][y] == ) return ;//出界或者有障碍物
else return ;
} void backtrack(int x, int y, int t) {
if (x == edX && y == edY || t > ) {//到达终点或者深度大于10
ans = (t < ans ? t : ans);//更新最短步数
}
else {
for (int i = ; i < ; i++) {//往四个方向试探
int tx = x, ty = y;
if (check(tx + stepX[i], y + stepY[i]) != ) { //可以往当前方向运动
while (check(tx + stepX[i], ty + stepY[i]) == ) { //没有障碍物 或 未到达终点的话就一直运动下去
tx += stepX[i], ty += stepY[i];
}
if (map[tx + stepX[i]][ty + stepY[i]] == ) {//遇到障碍物停止运动
map[tx + stepX[i]][ty + stepY[i]] = ;//击碎障碍物
t++; //步数加1
backtrack(tx, ty, t);//继续从障碍物前一个格子开始走
--t; //回溯时恢复现场
map[tx + stepX[i]][ty + stepY[i]] = ;
}
else if (map[tx + stepX[i]][ty + stepY[i]] == ) {//遇到终点停止运动
t++;
backtrack(tx + stepX[i], ty + stepY[i], t);
}
}
}
}
} int main() {
while (scanf("%d%d", &w, &h), w || h) {
memset(map, -, sizeof(map));
stX = stY = edX = edY = -;
for (int i = ; i <= h; i++) {
for (int j = ; j <= w; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == ) stX = i, stY = j; //起点
else if (map[i][j] == ) edX = i, edY = j;//终点
}
}
ans = MAXN;
backtrack(stX, stY, );
printf("%d\n", ans > ? - : ans);
}
return ;
}
2018-05-27