【汇编语言实战】解迷宫问题

简介: 【汇编语言实战】解迷宫问题

有一个 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


运行结果:

目录
相关文章
|
6月前
|
C语言
【汇编语言实战】实现九九乘法表
【汇编语言实战】实现九九乘法表
53 2
|
6月前
|
C语言
【汇编语言实战】输入一个无符号整数求其逆序
【汇编语言实战】输入一个无符号整数求其逆序
45 2
|
6月前
|
C语言
【汇编语言实战】两个32位数的相加运算
【汇编语言实战】两个32位数的相加运算
55 2
|
6月前
|
C语言
【汇编语言实战】八皇后问题
【汇编语言实战】八皇后问题
40 2
|
6月前
|
C语言
【汇编语言实战】实现输出集合{1,2,...,n}全排列
【汇编语言实战】实现输出集合{1,2,...,n}全排列
42 1
|
6月前
|
C语言
【汇编语言实战】给定一个句子,将大写字母变为小写
【汇编语言实战】给定一个句子,将大写字母变为小写
63 1
|
6月前
|
C语言
【汇编语言实战】最小公倍数和最大公约数
【汇编语言实战】最小公倍数和最大公约数
84 1
|
6月前
|
C语言
【汇编语言实战】二分查找
【汇编语言实战】二分查找
49 1
|
6月前
|
C语言
【汇编语言实战】正整数的素数分解
【汇编语言实战】正整数的素数分解
38 1
|
6月前
|
C语言
【汇编语言实战】冒泡排序
【汇编语言实战】冒泡排序
52 1
【汇编语言实战】冒泡排序