1 条题解
-
0
C :
#include <stdio.h> #include <malloc.h> #define M 50 // 迷宫行数(包括外墙) #define N 50 // 迷宫列数(包括外墙) #define D 4 // 移动方向数 struct { int x,y; #if D==4 }move[D]={{0,1},{1,0},{0,-1},{-1,0}}; #endif // 元素类型 typedef struct { int x,y; // 当前点的行值,列值 int pre; // 前一点在队列中的序号 } QElemType; #define MAXQSIZE 251 // 最大队列长度(对于循环队列,最大队列长度要减1) typedef struct { QElemType *base;// 初始化的动态分配存储空间 相当于一个数组 int front; int rear; }SqQueue; //初始化队列为空 int InitQueue(SqQueue *Q) { Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q->base) return 0; Q->front=Q->rear=0; return 1; } // 判断队列是否为空 int QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } // 入队 int EnQueue(SqQueue *Q,QElemType e) { if((Q->rear+1)%MAXQSIZE == Q->front) return (0);//队列满 Q->base[Q->rear] = e;//从队尾插入元素 Q->rear = (Q->rear+1) % MAXQSIZE; return 1; } // 出队 int DeQueue(SqQueue *Q,QElemType *e) { if(Q->front == Q->rear) return 0;// 队列空 *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXQSIZE; return 1; } // 广度搜索法求一条迷宫路径 int Path(char maze[M][N]) { SqQueue q; QElemType cur,next; // 当前点和下一点 int i,flag=1; // 当找到出口,flag=0 int x1, y1; // 终点的坐标 //当前点入口为(0,0)点 cur.x=0; cur.y=0; cur.pre = -1; // 设入口(第一点)的上一点的序号=-1 maze[cur.x][cur.y] = -1; // 初始点设为已访问过 InitQueue(&q); EnQueue(&q,cur); // 起点入队 while(!QueueEmpty(q)&&flag) { DeQueue(&q,&cur); // 出队qf为当前点 for(i=0;i<D;i++) // 向各个方向尝试 { // 下一点的坐标,正东起顺时针4个方向 next.x=cur.x+move[i].x; next.y=cur.y+move[i].y; if(maze[next.x][next.y] == ' ') { maze[next.x][next.y] = -1; // 已访问过 next.pre=q.front-1; EnQueue(&q,next); // 将下一点入队 } if(maze[next.x][next.y] == 'B') // 到达终点 { flag=0; x1=next.y; y1=next.x; break; } } } if(flag) // 搜索完整个队列还没到达终点 { printf("Box is not found.\n"); return 0; } else { printf("Box is found at x=%d y=%d.\n",x1,y1); return 1; } } int main() { int n,m; char map[M][N]; // 迷宫数组 while(scanf("%d%d\n",&n,&m)==2) //能够读到两个数字说明还有输入要处理 { for (int i=0;i<n;i++) gets(map[i]);//读取第i行 Path(map); } return 0; }
- 1
信息
- ID
- 243
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者