Máš vôbec predstavu, akým tempom rastie počet všetkých ciest s každým zväčšením mriežky? Je to viac než exponenciálne:

2x2	          4
3x3	         20
4x4	        548
5x5	     40 440
6x6	  8 442 742
7x7	793 515 676

Neviem si predstaviť, načo by si chcel tie cesty ešte aj niekam vypisovať. Len na vypísanie ciest by si potreboval viac než 10 GB miesta (ak 1 krok = 1 bajt).

Prvá optimalizácia by mohla byť taká, že využiješ symetriu: Na začiatku, keď ideš z pozície [1,1] buď na [2,1] alebo na [1,2], preskúmaš len jednu z týchto možností a počet ciest potom prenásobíš dvoma - takáto optimalizácia ti celý výpočet dvojnásobne zrýchli. Podobné finty ti môžu podstatne zrýchliť celý výpočet. Ďalšia optimalizácia by bola zbavenie sa tej rekurzie.

Otázka je, prečo niečo takéto vôbec potrebuješ robiť a tiež to, či ti nevadí, že nájdená cesta nemusí prejsť celú mriežku.