HDOJ 1253 승리 대도 망 (bfs)
7908 단어 bfs
사고 분석: 문 제 는 종점 에 도착 하 는 가장 짧 은 거리 (가장 짧 은 걸음 수) 를 찾 아야 하기 때문이다. 즉, 상태 전환 도 에서 가장 얕 은 상 태 를 찾 아야 한다 (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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
나무깊이 우선 탐색(DFS) 깊이 우선 검색(DFS)은 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기 위한 알고리즘입니다. 하나는 루트에서 시작하여(그래프의 경우 임의의 노드를 루트로 선택) 역추적하기 전에 각 분...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.