HDU 1728 逃离迷宫 + HDU 1072 Nightmare
KIDx 的解题报告
HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
对于代码31行，为什么等于不能随便剪掉
如果剪掉就会出现下图结果：
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的，由于最多转一次弯，所以不合题意；
蓝色是后搜的，因为遇到转弯数相等所以不往下走了了，但是继续走是可以满足题意输出"yes"的
深搜：
#include <iostream>#include <queue>using namespace std;#define inf 0x3fffffff#define M 10int sx, sy, step[M][M], T[M][M], r, c;int x_move[4] = {-1, 0, 1, 0};int y_move[4] = {0, 1, 0, -1};int map[M][M];struct pos{ int x, y;};void bfs (){ int i, j; for (i = 0; i < r; i++) for (j = 0; j < c; j++) step[i][j] = inf, T[i][j] = 0; pos ft, tp; ft.x = sx, ft.y = sy; step[ft.x][ft.y] = 0; T[ft.x][ft.y] = 6; queue <pos> q; q.push (ft); while (!q.empty()) { ft = q.front(); q.pop(); if (map[ft.x][ft.y] == 3 && T[ft.x][ft.y] > 0) { printf ("%d\n", step[ft.x][ft.y]); return ; } for (i = 0; i < 4; i++) { tp.x = ft.x + x_move[i]; tp.y = ft.y + y_move[i]; if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c) continue; if (map[tp.x][tp.y] == 0) continue; if (step[tp.x][tp.y] <= step[ft.x][ft.y] + 1 && T[tp.x][tp.y] >= T[ft.x][ft.y] - 1) continue; step[tp.x][tp.y] = step[ft.x][ft.y] + 1; T[tp.x][tp.y] = T[ft.x][ft.y] - 1; if (T[tp.x][tp.y] <= 0) continue; if (map[tp.x][tp.y] == 4) T[tp.x][tp.y] = 6; q.push (tp); } } puts ("-1");}int main(){ int t, i, j; scanf ("%d", &t); while (t--) { scanf ("%d%d", &r, &c); for (i = 0; i < r; i++) { for (j = 0; j < c; j++) { scanf ("%d", map[i]+j); if (map[i][j] == 2) sx = i, sy = j; } } bfs (); } return 0;}