HDOJ 1253 승리 대도 망 (bfs)

7908 단어 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 = 60;
struct Point
{
    int a, b, c;
    int time;
    Point() { a = 0; b = 0; c = 0; time = 0; }
    Point(int x, int y, int z, int step_time)
    {
        a = x; b = y; c = z; time = step_time;
    }
};

int ans = 0;
int A, B, C, game_times;
int map[MAX_N][MAX_N][MAX_N];
int move[6][3] =
{{0, 0, -1}, {0, 0, 1}, {0, -1, 0}, {0, 1, 0}, {-1, 0, 0}, {1, 0, 0}};
Point queue[1000000];

int Bfs()
{
    int head, tail;
    Point temp;

    head = tail = 0;
    temp.a = temp.b = temp.c = temp.time = 0;
    queue[tail++] = temp;

    while (head != tail)
    {
        temp = queue[head++];
        for (int i = 0; i < 6; ++i)
        {
            int next_a = temp.a + move[i][0];
            int next_b = temp.b + move[i][1];
            int next_c = temp.c + move[i][2];

            if (next_a < 0 || next_b < 0 || next_c < 0
                || next_a >= A || next_b >= B || next_c >= C
                || map[next_a][next_b][next_c] > 0 || temp.time + 1 > game_times)
                continue;

            if (next_a == A - 1 && next_b == B - 1 && next_c == C - 1)
                return temp.time + 1;

            Point next(next_a, next_b, next_c, temp.time + 1);
            map[next_a][next_b][next_c] = next.time;
            queue[tail++] = next;
        }
    }
    return  -1;
}

int main()
{
    int k;

    scanf("%d", &k);
    while (k--)
    {
        scanf("%d %d %d %d", &A, &B, &C, &game_times);
        for (int i = 0; i < A; ++i)
        for (int j = 0; j < B; ++j)
        for (int k = 0; k < C; ++k)
            scanf("%d", &map[i][j][k]);

        printf("%d
", Bfs()); } return 0; }

좋은 웹페이지 즐겨찾기