题意:在矩形冰面进行滑石头游戏,只能上下左右滑,冰面上散步很多障碍,给定石头初始位置和需要到达的终点以及障碍的分布。
若石头与障碍物相邻,则石头不能向这个方向滑动; 若石头滑动起来后,便会一直沿这个方向滑动,若出界,则游戏失败,若碰到障碍物,则石头停下,障碍物消失,
若石头到达终点,则游戏结束。注意石头滑动次数不能超过10次,这是很重要的剪枝
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define INF 15 int w, h, step[4][2] = {{0, -1}, { -1, 0}, {0, 1}, {1, 0}}; int map[25][25]; inline int min(int a, int b) { return a > b ? b : a; } int dfs(int x, int y, int stp) //stp记录滑动次数 { int tx, ty, tmp = INF; if (stp >= 10) return INF; //超过十次,剪枝 for (int i = 0; i < 4; i++) { bool flag = false; tx = x; ty = y; while (true) { tx += step[i][0]; ty += step[i][1]; if (tx >= 0 && tx < h && ty >= 0 && ty < w) { if (map[tx][ty] == 1) { if (!flag) break; else { map[tx][ty] = 0; tmp = min (tmp, 1 + dfs(tx - step[i][0], ty - step[i][1], stp + 1)); map[tx][ty] = 1; break; } } else if (map[tx][ty] == 3) return 1; else { flag = true; } } else break; } } return tmp; } int main() { int i, j, sx, sy; while (scanf("%d %d", &w, &h) && w && h) { for (i = 0; i < h; i++) for (j = 0; j < w; j++) { scanf("%d", &map[i][j]); if (map[i][j] == 2) { sx = i; sy = j; } } int ans = dfs(sx, sy, 0); if (ans > 10) printf("-1\n"); else printf("%d\n", ans); } return 0; }