查找从左上角到右下角组件的所有路径。

Question

我是装配编程的新手，目前正在上在线课程。

最初的问题是从左上角到右下角的路径数。但我在这里找到了一个很好的解决方案：

https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/

根据组合学解，我应该能够以二进制方式找到所有的路径。第一个问题，你知道如何更快地计算路径吗？

搜索要打印以下所有路径的解决方案：

https://www.geeksforgeeks.org/print-all-possible-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/

但是没有注意到任何使用二进制方法的方法似乎适合组装。在网上搜索我发现：

https://www.baeldung.com/cs/generate-k-combinations

旋转门算法非常详细，我计算出它是O(组合数)*O(矩阵的宽度或高度(用于打印) -1) *O(分支循环)在时间复杂度上，O(宽度或高度+ 1)在空间。第二个问题，这是否正确的假设？如果没有，正确的复杂性是什么？它是否比发布的其他解决方案更快，以找到解决这个问题的所有途径？说明为O(2^(宽度*高度))

第三个问题:这个算法是谁写的？我在哪里能找到更像它的？

最后，我将张贴我的新的32位组装面食代码，如果工作的矩阵大于3x3小于32x32(不建议超过16x16，这是很多组合，只是省略打印说明)，任何改进都是非常受欢迎的。谢谢。

    format PE console
entry start



include 'win32a.inc' 

; ===============================================
struct MAT
    h   db  ?       ; X coordinate.
    w   db  ?       ; Y coordinate.
ends



; ===============================================
section '.bss' readable writeable
    ; Declare the uninitialized table in memory:
    path_matrix     MAT  ?
    count           dd  ?
    indices         db path_matrix.w - 1 dup ?
    end_indices:
    

; ===============================================
section '.text' code readable executable

start:

    call    read_hex
    mov     [path_matrix.h], al ; down will be 0
    call    read_hex
    mov     [path_matrix.w], al ; right will be 1
    
    dec     eax
    mov     ecx, eax
    
initialize: 
    mov     ebx, ecx
    dec     ebx
    mov     byte[indices+ecx], bl
    loop    initialize
    movzx   ebx, [path_matrix.h]
    dec     ebx
    add     ebx, eax
    mov     byte[indices+eax+1], bl 
    mov     eax, ebx
    
    

print_combination:
    inc     [count]
    movzx   ebx, [end_indices - indices]
    dec     ebx
    xor     eax, eax
    
    
print_loop:
    xor     esi, esi
    inc     esi
    mov     cl, byte[indices + ebx ]
    shl     esi, cl
    xor     eax, esi
    dec     ebx
    cmp     ebx, 0
    jnz     print_loop
    call    print_eax_binary


    
branch:
    lea     edi, [indices +1]
    movzx   eax, [path_matrix.w] ; check if withd is eaven, if true matrix is odd (w -1)
    shr     eax, 1
    jnc     odd
    

eaven:
    movzx   eax, byte[edi]
    cmp     eax, 0
    jle     eaven_indice
    dec     eax
    mov     byte[edi], al
    jmp     print_combination 
    

eaven_indice:
    inc     edi
        

try_to_increase:
    movzx   ebx, byte[edi]
    inc     ebx
    cmp     bl, [edi+1]
    jl      increase
    lea     ecx, [edi-indices+1]
    cmp     cl, [path_matrix.w]
    jl      increase_indice
    jmp     fin
    
    
increase:
    mov     byte[edi], bl
    dec     ebx
    mov     byte[edi-1], bl
    jmp     print_combination

    
    
odd:
    movzx   eax, byte[edi]
    inc     eax
    cmp     al, [edi+1]
    jge     increase_indice
    mov     byte[edi], al
    jmp     print_combination

    
increase_indice:
    inc     edi
    

try_decrease:
    lea     eax, [edi - indices]
    cmp     byte[edi], al
    jl      eaven_indice    

    
decrease:
    movzx   ebx, byte[edi-1]
    mov     byte[edi], bl
    sub     eax, 2
    mov     byte[edi-1], al
    jmp     print_combination
    
    
fin:
    mov     eax, [count]
    call    print_eax

    ; Exit the process:
    push    0
    call    [ExitProcess]

include 'training.inc'

Answer 1

解决方案不是二进制的，因为来自顶部或左侧的路径可能重叠--创建重复项。向后工作，解是从左到上路径的相加和。

这导致了一个简单的解决方案：

_m      = 16
_n      = 16

ddp     rq _m

        ; initialize first position
        mov [ddp + (_n-1)*8], 1
        mov ecx, _m
outer:
        push rcx
        mov ecx, _n
        xor eax, eax
inner:
        add rax, [ddp + (rcx-1)*8]
        mov [ddp + (rcx-1)*8], rax
        loop inner
        pop rcx
        loop outer

有一个封闭的表单解决方案，但要减少表达式以涵盖大量输入是有点棘手的：

; number of paths from one corner to opposite diagonal corner of M x N matrix
; RCX : N, RDX : M
numberOfPaths:
        mov eax,1
        mov r9,1
        lea r8,[rcx+rdx-1]
        jmp .try
    .more:
        mul rcx
        inc ecx
        div r9
        inc r9
    .try:
        cmp rcx,r8
        jc .more
        retn

它可以通过更多的代码进一步减少。