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;}