Cho một ma trận vuông kích thước N*M chỉ chứa các số nguyên không âm. Ban đầu đặt một robot ở ô (1,1), yêu cầu tìm đường đi đến ô (N, M) sao cho chi phí thu được là nhỏ nhất. Biết rằng, tại ô (i, j) chỉ được đi sang ô (i+1, j) hoặc (i, j+1). Chi phí của đường đi được xác định bằng số chữ số 0 tận cùng của tích các số trên đường đi.
Input:
- Dòng đầu tiên chứa số nguyên N, M (N, M ≤ 1000) là kích thước của ma trận
- N dòng tiếp theo, mỗi dòng chứa M số nguyên không âm và không vượt quá 109
Output: Một số nguyên duy nhất là chi phí của đường đi nhỏ nhất tìm được.
Ví dụ:
Input:
4 3
1 2 3
4 5 6
7 8 9
10 11 12
Output:
0
Giải thích: các cách đi thu được chi phí là 0:
- 1 → 2 → 3 → 6 → 9 → 12, 1*2*3*6*9*12 = 3888
- 1 → 4 → 7 → 8 → 9 → 12, 1*4*7*8*9*12 = 24192
- 1 → 4 → 7 → 8 → 11 → 12, 1*4*7*8*11*12 = 29568
Loga
Sinh Học lớp 12
