HDOJ 1253 胜利大逃亡（bfs）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1253

思路分析：因为问题需要寻找到达终点的最短的距离(最短的步数)，即在状态转换图上需要找出层次最浅的的状态(A-1, B-1, C-1)，

所以采用bfs更快能找出答案；另外，若采用dfs则比较困难，需要遍历所有的状态才能找出结果。

代码如下：

#include <cstdio>

#include <iostream>

const int MAX_N = ;

struct Point

{

    int a, b, c;

    int time;

    Point() { a = ; b = ; c = ; time = ; }

    Point(int x, int y, int z, int step_time)

    {

        a = x; b = y; c = z; time = step_time;

    }

};

int ans = ;

int A, B, C, game_times;

int map[MAX_N][MAX_N][MAX_N];

int move[][] =

{{, , -}, {, , }, {, -, }, {, , }, {-, , }, {, , }};

Point queue[];

int Bfs()

{

    int head, tail;

    Point temp;

    head = tail = ;

    temp.a = temp.b = temp.c = temp.time = ;

    queue[tail++] = temp;

    while (head != tail)

    {

        temp = queue[head++];

        for (int i = ; i < ; ++i)

        {

            int next_a = temp.a + move[i][];

            int next_b = temp.b + move[i][];

            int next_c = temp.c + move[i][];

            if (next_a <  || next_b <  || next_c <

                || next_a >= A || next_b >= B || next_c >= C

                || map[next_a][next_b][next_c] >  || temp.time +  > game_times)

                continue;

            if (next_a == A -  && next_b == B -  && next_c == C - )

                return temp.time + ;

            Point next(next_a, next_b, next_c, temp.time + );

            map[next_a][next_b][next_c] = next.time;

            queue[tail++] = next;

        }

    }

    return  -;

}

int main()

{

    int k;

    scanf("%d", &k);

    while (k--)

    {

        scanf("%d %d %d %d", &A, &B, &C, &game_times);

        for (int i = ; i < A; ++i)

        for (int j = ; j < B; ++j)

        for (int k = ; k < C; ++k)

            scanf("%d", &map[i][j][k]);

        printf("%d\n", Bfs());

    }

    return ;

}