Chúng ta coi hành trình đi và về là hai hành trình song song cùng xuất phát từ ô (1,1). Tiếp theo, chúng ta loang tìm tất cả các ô có thể tới được từ ô (1,1) (bởi nếu không tới được mà cộng vào kết quả sẽ gây ra kết quả sai, nhìn test ví dụ ở dưới sẽ rõ :D ). Cuối cùng là quy hoạch động, gọi f[i][j][k] là tới hàng i, hàng j sau k bước (sẽ tính được tọa độ của cột), tìm mối liên hệ với các ô có thể tới được bằng BFS từ trước. Kết quả F[n][m][n+m-2].

Test ví dụ:

4 3

...

##.

.*.

...

->Kết quả ra 0, bởi nếu ăn ô * sẽ đi vào đường cụt và không thể tới ô (n,m) hay về ô (1,1)