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

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(*0(分支循环(，在空间上是0(宽度或高度+1(。第二个问题，这是一个正确的假设吗？如果不是，正确的复杂性是多少？它是否比发布的其他解决方案更快地找到解决此问题的所有路径？这些规定为O(2^(宽*高((

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

最后，我将为fasm发布我的新手32位汇编意大利面代码，它应该适用于大于3 x 3小于32 x 32的矩阵(不建议超过16 x 16，这已经是很多组合了，只是省略了打印说明(，任何改进都是非常受欢迎的。非常感谢。

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

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