题意：
给出一个w*h的地图，其中0代表空地，1代表障碍物，2代表起点，3代表终点，每次行动可以走多个方格，每次只能向附近一格不是障碍物的方向行动，直到碰到障碍物才停下来，此时障碍物也会随之消失,如果行动时超出方格的界限或行动次数超过了10则会game over .如果行动时经过3则会win，记下此时行动次数（不是行动的方格数），求最小的行动次数
#include#include #include using namespace std;typedef long long LL;const int INF = 0x7FFFFFFF;const int maxn = 1e5 + 10;int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };int ei, ej;int map[25][25];int w, h, steps, MIN;#define MAX 99999999void dfs(int si, int sj){ int i, pi, pj; if (steps >= 10) return; for (i = 0; i<4; i++) { pi = si, pj = sj; while (1) { pi += dir[i][0]; pj += dir[i][1]; if (pi <= 0 || pi>h || pj <= 0 || pj > w) break;//如果越界，选择其他方向 if (pi == ei&&pj == ej) { steps++; if (MIN > steps) MIN = steps; steps--; return; } else if (map[pi][pj] == 1)//如果遇到障碍物 { if(pi-dir[i][0]!=si||pj-dir[i][1]!=sj)//如果不是起步 { map[pi][pj] = 0;//消除障碍物 steps++;//前进一步 dfs(pi - dir[i][0], pj - dir[i][1]);//递归查找该点到终点的最小步数 map[pi][pj] = 1;//还原障碍物 steps--;//还原步数 } break; } } }}int main(){ int si, sj, i, j; while (scanf("%d%d", &w, &h) == 2 && (w || h)) { for (i = 1; i <= h; i++)//输入并找到起点和终点 for (j = 1; j <= w; j++) { scanf("%d", &map[i][j]); if (map[i][j] == 2) si = i, sj = j; else if (map[i][j] == 3) ei = i, ej = j; } MIN = MAX;//记录最小步数 steps = 0;//初始化步数 dfs(si, sj);//深搜 if (MIN == MAX) puts("-1"); else printf("%d\n", MIN); } return 0;}