胜利大逃亡(bfs)
题目
#include <stdio.h>#include <stdlib.h> #define QUEUESIZE 51 * 51 * 51#define MAX 1005 int direction[6][3] = {{0, 0, 1}, {0, 0, -1}, {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}}; int A, B, C, T, spend, maze[51][51][51]; struct node{ int x, y, z; int time;}; struct queue{ struct node data[QUEUESIZE]; int front, rear, count;}; void en_queue(struct queue *Q, struct node p);struct node de_queue(struct queue *Q);int breadth_first_search(); int main(){ int n, x, y, z; scanf("%d", &n); while (n --) { scanf("%d %d %d %d", &A, &B, &C, &T); for (z = 0; z < A; z ++) { for (x = 0; x < B; x ++) { for (y = 0; y < C; y ++) { scanf("%d", &maze[z][x][y]); } } } if (A + B + C - 3 > T) { printf("-1\n"); }else if (maze[A - 1][B - 1][C - 1] == 1) { printf("-1\n"); }else if (A == 1 && B == 1 && C == 1) { printf("0\n"); }else { spend = breadth_first_search(); printf("%d\n", spend); } } return 0;} /** * Description:入队操作 */void en_queue(struct queue *Q, struct node p){ if (Q->count < QUEUESIZE) { Q->data[Q->rear] = p; Q->count ++; Q->rear += 1; }else { exit(-1); }} /** * Description:出队操作 */struct node de_queue(struct queue *Q){ if (Q->count > 0) { struct node p; p = Q->data[Q->front]; Q->front += 1; Q->count --; return p; }else { exit(-1); }} /** * Description:广度优先搜索 */int breadth_first_search(){ int i, tz, tx, ty; struct node s, u, p; // 初始化bfs起始节点 s.x = s.y = s.z = s.time = 0; maze[0][0][0] = 1; // 初始化队列 struct queue *Q = (struct queue *)malloc(sizeof(struct queue)); Q->front = Q->rear = Q->count = 0; // 初始节点入队列 en_queue(Q, s); while (Q->count != 0) { u = de_queue(Q); if (u.z == A - 1 && u.x == B - 1 && u.y == C - 1 && u.time <= T) { return u.time; } for (i = 0; i < 6; i ++) { tz = u.z + direction[i][0]; tx = u.x + direction[i][1]; ty = u.y + direction[i][2]; if (tz >= 0 && tz < A && tx >= 0 && tx < B && ty >= 0 && ty < C && maze[tz][tx][ty] == 0) { maze[tz][tx][ty] = 1; p.x = tx; p.y = ty; p.z = tz; p.time = u.time + 1; en_queue(Q, p); } } } return -1;}/************************************************************** Problem: 1456 User: wangzhengyi Language: C Result: Accepted Time:30 ms Memory:32568 kb****************************************************************/