有一个 7 x 7 的迷宫,起点是’S’,终点是’E’,墙是’o’,道路是空格。
请找出从起点到终点的通路,通路用符号’.'表示。
用二维数组表示迷宫场景。其中用2代表迷宫的墙壁,0代表可行通道。
走的路径记作1,也就是数组中的0被改为1。
C语言描述:
#include <stdio.h> #include <stdlib.h> #define M 9 //把7*7迷宫加大成9*9格局 int maze[M][M] ={ {2,2,2,2,2,2,2,2,2}, {2,0,0,0,0,0,0,0,2}, {2,0,2,2,0,2,2,0,2}, {2,0,2,0,0,2,0,0,2}, {2,0,2,0,2,0,2,0,2}, {2,0,0,0,0,0,2,0,2}, {2,2,0,2,2,0,2,2,2}, {2,0,0,0,0,0,0,0,2}, {2,2,2,2,2,2,2,2,2} }; int start1=1,start2=1; //假定[1][1]是入口 int end1=7, end2=7; //假定[7][7]是出口 void visit(int i,int j){ int m,n; maze[i][j] = 1; if(i==end1 && j==end2) { //判断是否到达出口位置,到达直接输出 printf("\n显示路径:\n"); for(m=0;m<M;m++){ for(n=0;n<M;n++){ if(maze[m][n] == 2) printf("o"); else if(maze[m][n] == 1) printf("."); else printf(" "); } printf("\n"); }//end for }//end if //不再判定是否到达出口,只分析老鼠可以在迷宫移动的方向, //并递归求下一步. if(maze[i][j+1] == 0) visit(i,j+1); if(maze[i+1][j] == 0) visit(i+1,j); if(maze[i][j-1] == 0) visit(i,j-1); if(maze[i-1][j] == 0) visit(i-1,j); //若代码运行到这一步,则证明前面走的路径并不能到达出口, //则返回,把走过的位置重新写作0 maze[i][j] = 0; } int main (){ int i,j; printf("显示迷宫:\n"); for(i=0;i<M;i++) { //对摆放的数组迷宫进行打印 for(j=0;j<M;j++) if(maze[i][j] == 2) printf("o"); else printf(" "); printf("\n"); } visit(start1,start2); //直接调用visit函数,把输出内容放在visit函数中, //好让所有路径进行遍历 return 0; }
汇编语言:
INCLUDE Irvine32.inc .data maze dd 2,2,2,2,2,2,2,2,2 dd 2,0,0,0,0,0,0,0,2 dd 2,0,2,2,0,2,2,0,2 dd 2,0,2,0,0,2,0,0,2 dd 2,0,2,0,2,0,2,0,2 dd 2,0,0,0,0,0,2,0,2 dd 2,2,0,2,2,0,2,2,2 dd 2,0,0,0,0,0,0,0,2 dd 2,2,2,2,2,2,2,2,2 rowsize dd ($-maze)/9 M dd 9 start1 dd 1 start2 dd 1 end1 dd 7 end2 dd 7 present db 'present the chess',0 present_path db 'present the path',0 cnt dd 0 one dd 1 .code main PROC mov edx,offset present call writeString call crlf call print_chess push start2 push start1 call visit exit main ENDP print_chess PROC push ebp mov ebp,esp pushad mov esi,0 for_0: cmp esi,M jge final mov edi,0 for_1: ;涉及乘除运算的时候不要使用edx cmp edi,M jge for_0_end mov ebx,offset maze mov eax,rowsize mul esi add ebx,eax mov ecx,[ebx+edi*4] mov eax,ecx; ; call writedec cmp eax,2 jne else_0 mov al,'o' call writechar jmp for_1_end else_0: mov al,' ' call writechar for_1_end: inc edi jmp for_1 for_0_end: call crlf inc esi; jmp for_0 final: popad pop ebp ret print_chess ENDP visit PROC push ebp mov ebp,esp pushad mov esi,[ebp+8] ;esi:i mov edi,[ebp+12] ;edi:j mov ebx,offset maze ;ebx:maze mov eax,esi mul rowsize add ebx,eax mov eax,1 mov [ebx+edi*4],eax ; call crlf ; mov eax,esi ; call crlf ; call writedec ; call crlf ; mov eax,edi ; call writedec ; call crlf cmp esi,end1 jne dfs cmp edi,end2 jne dfs mov edx,offset present_path call writeString call crlf push edi push esi call output dfs: mov ebx,offset maze mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi mul rowsize add ebx,eax mov eax,0 cmp [ebx+edi*4+4],eax jne vis_1 mov esi,[ebp+8] mov edi,[ebp+12] mov eax,edi inc eax push eax push esi call visit vis_1: mov ebx,offset maze mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi inc eax mul rowsize add ebx,eax mov eax,0 cmp [ebx+edi*4],eax jne vis_2 mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi inc eax push edi push eax call visit vis_2: mov ebx,offset maze mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi mul rowsize add ebx,eax mov eax,0 cmp [ebx+edi*4-4],eax jne vis_3 mov esi,[ebp+8] mov edi,[ebp+12] mov eax,edi sub eax,1 push eax push esi call visit vis_3: mov ebx,offset maze mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi dec eax mul rowsize add ebx,eax mov eax,0 cmp [ebx+edi*4],eax jne final mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi sub eax,1 push edi push eax call visit final: mov ebx, offset maze mov esi,[ebp+8] mov edi,[ebp+12] mov eax,esi mul rowsize add ebx,eax mov eax,0 mov [ebx+edi*4],eax popad pop ebp ret 8 visit ENDP output PROC push ebp mov ebp,esp pushad mov esi,0 for_0: cmp esi,M jge final mov edi,0 for_1: cmp edi,M jge for_0_end mov ebx,offset maze mov eax,esi mul rowsize add ebx,eax mov eax,2 cmp [ebx+edi*4],eax jne else_0 mov al,'o' call writechar jmp for_1_end else_0: mov ebx,offset maze mov eax,esi mul rowsize add ebx,eax mov eax,1 cmp [ebx+edi*4],eax jne else_1 mov al,'.' call writechar jmp for_1_end else_1: mov al,' ' call writechar for_1_end: inc edi jmp for_1 for_0_end: call crlf inc esi jmp for_0 final: popad pop ebp ret 8 output ENDP END main
运行结果: