cnx重庆面试测试题答案

cnx重庆面试测试题答案输入两个整数，N与M，分别代表二维数组的行数与列数。再输入对应的值，1代表墙壁，0代表可走的路，迷宫只有唯一一条通道可走。（0，0）为入口，（N-1，M-1）为出口，数据范围：2<=N<=10，2<=M<=10，数组中仅包含0和1，要求纵向输出从入口到出口的路径。解题思路深度优先搜索（DFS）结合栈：从入口开始探索，每次将走过的路标记为2（同时入栈）。如果走到某条不通的路线，就返回到该路线的起点处（把不通的路线出栈），接着尝试走没走过的路，直至找到出口。创建迷宫：动态开辟一个二维数组来存储迷宫，行数为N，列数为M，根据输入填充迷宫元素。路径存储与回溯：利用栈来存储路径，当找到出口时，栈中存储的就是从入口到出口的路径。如果遇到死路，通过出栈操作回溯到上一个可选择的位置。输出路径：由于栈的特性是后进先出，所以保存的路径是颠倒的。需要再利用一个栈将路径反转，然后纵向输出。代码实现#include<stdio.h>#include<stdlib.h>#include<stdbool.h>//定义结构体来存放迷宫坐标typedefstruct{introw;intcol;}path;//栈的结构体定义typedefstructStack{path*arr;inttop;intcapacity;}stack;//初始化栈voidStackInit(stack*s){s->arr=NULL;s->top=0;s->capacity=0;}//销毁栈voidStackDestroy(stack*s){if(s->arr!=NULL){free(s->arr);}s->arr=NULL;s->top=0;s->capacity=0;}//入栈操作voidStackPush(stack*s,pathp){if(s->top==s->capacity){intnewcapacity=s->capacity==0?4:2*s->capacity;path*tmp=(path*)realloc(s->arr,newcapacity*sizeof(path));if(tmp==NULL){perror("reallocfail!");exit(1);}s->arr=tmp;s->capacity=newcapacity;}s->arr[s->top]=p;s->top++;}//出栈操作voidStackPop(stack*s){if(s->top>0){s->top--;}}//获取栈顶元素pathStackTop(stack*s){if(s->top>0){returns->arr[s->top-1];}//这里可以返回一个特殊值表示栈为空，为简单起见，假设不会在空栈时调用}//判断栈是否为空boolStackEmpty(stack*s){returns->top==0;}//判断当前路径的坐标是否可走boolisPass(int**maze,intN,intM,pathcur){returncur.row>=0&&cur.row<N&&cur.col>=0&&cur.col<M&&maze[cur.row][cur.col]==0;}//寻找迷宫的出口路径boolFindMazeExit(int**maze,intN,intM,pathcur,stack*exitPath){StackPush(exitPath,cur);maze[cur.row][cur.col]=2;pathnext=cur;//向迷宫的上方寻找next.row-=1;if(isPass(maze,N,M,next)){if(FindMazeExit(maze,N,M,next,exitPath)){returntrue;}}//向迷宫的下方寻找next=cur;next.row+=1;if(isPass(maze,N,M,next)){if(FindMazeExit(maze,N,M,next,exitPath)){returntrue;}}//向迷宫的左方寻找next=cur;next.col-=1;if(isPass(maze,N,M,next)){if(FindMazeExit(maze,N,M,next,exitPath)){returntrue;}}//向迷宫的右方寻找next=cur;next.col+=1;if(isPass(maze,N,M,next)){if(FindMazeExit(maze,N,M,next,exitPath)){returntrue;}}StackPop(exitPath);returnfalse;}//输出迷宫的出口路径voidPrintMazeExitPath(stackp){stackreversePath;StackInit(&reversePath);while(!StackEmpty(&p)){StackPush(&reversePath,StackTop(&p));StackPop(&p);}while(!StackEmpty(&reversePath)){pathcur=StackTop(&reversePath);printf("(%d,%d)\n",cur.row,cur.col);StackPop(&reversePath);}StackDestroy(&reversePath);}intmain(){intN=0,M=0;while(scanf("%d%d",&N,&M)!=EOF){int**maze=(int**)malloc(sizeof(int*)*N);for(inti=0;i<N;i++){maze[i]=(int*)malloc(sizeof(int)*M);}for(inti=0;i<N;i++){for(intj=0;j<M;j++){scanf("%d",&maze[i][j]);}}pathcur={0,0};stackexitPath;StackInit(&exitPath);if(FindMazeExit(maze,N,M,cur,&exitPath)){PrintMazeExitPath(exitPath);}StackDestroy(&exitPath);for(inti=0;i<N;i++){free(maze[i]);}free(maze);}return0;}代码说明数据结构定义：path结构体用于存放迷宫中的坐标。stack结构体实现了一个简单的栈，用于存储路径。栈操作函数：StackInit：初始化栈。StackDestroy：销毁栈，释放内存。StackPush：将元素入栈，动态扩容栈空间。StackPop：将栈顶元素出栈。StackTop：获取栈顶元素。StackEmpty：判断栈是否为空。核心逻辑函数：isPass：判断当前坐标是否可走，即是否在迷宫范围内且对应位置为0。FindMazeE