Số đường đi
Submit solution
Points:
4
Time limit:
1.0s
Memory limit:
10M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Cho ma trận N x M chứa các giá trị:
- 1: biểu diễn điểm bắt đầu.
- 2: biểu diễn điểm kết thúc.
- 0: biểu diễn ô trống.
- -1: biểu diễn chướng ngại vật.
Một con robot đang đứng ở vị trí 1, nó có thể di chuyển theo 4 hướng: lên, xuống, trái, phải.
Hay tìm số cách để robot đi từ điểm bắt đầu đến điểm kết thúc sao cho đi qua mỗi ô trống một lần (điểm bắt đầu và điểm kết thúc được xem như ô trống).
Input
Dòng đầu chứa số nguyên T là số bộ test (1 <= T <= 20)
T dòng tiếp:
Dòng đầu chứa 2 số nguyên N, M là kích thước của ma trận (2 <= N x M <= 20)
N dòng tiếp theo, mỗi dòng chứa M số nguyên có giá trị -1, 0, 1 hoặc 2.
Input đảm bảo ma trận luôn có duy nhất một giá trị 1 và một giá trị 2.
Output
với mỗi bộ test, in ra số cách đi trên từng dòng.
Input
2
2 2
0 1
2 0
1 2
1 2Output
0
1
Comments
Chú ý, có bao nhiêu số 0 phải đi qua tất cả các số 0 đó