Công ty AZ đang sản xuất robot vận chuyển hàng hóa tự động trên mặt đất. Để làm việc đó, AZ tiến hành huấn luyện robot trên một địa hình phẳng được chia thành một lưới các ô vuông gồm m dòng (đánh số từ 1 đến m) và n cột (đánh số từ 1 đến n). Ô nằm giao giữa dòng i, cột j được gọi là ô (i,j) và chứa số nguyên dương cij.
Robot có kích thước bằng đúng một ô vuông. Ban đầu, robot đang ở ô (1,1), robot có thể di chuyển sang ô (1,2) hoặc ô (2,1). Sau bước di chuyển đầu tiên, số lần robot rẽ trái sẽ được kiểm soát. Robot cần tìm đường đi đến ô (m,1) theo quy tắc: tại mỗi ô, robot có thể di chuyển sang ô chung cạnh với ô đó, không được đi ra ngoài bảng và số lần rẽ trái không vượt quá k. Việc đánh giá cho điểm một đường đi được dựa trên số lượng số 0 liên tiếp nằm ở cuối của tích các số trong các ô thuộc đường đi, số lượng số 0 càng ít thì càng được đánh giá cao.
Yêu cầu: Cho bảng số, tìm đường đi có số lượng số 0 liên tiếp nằm ở cuối của tích các số trong ô thuộc đường đi là ít nhất.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên m,n,k (k≤30);
m dòng tiếp theo, mỗi dòng n số nguyên dương mô tả bảng số.
Kết quả:
Đưa ra một số nguyên là số lượng số 0 liên tiếp nằm ở cuối của tích các số trong các ô thuộc đường đi tìm được.
Input
5 5 1
1 1 1 1 1
20 20 20 20 1
1 1 1 10 1
1 20 1 20 1
5 20 1 1 1
Output
1
Ràng buộc:
Có 30% số test ứng với 30% số điểm có m,n≤30 và cij có dạng 10^p (p≤9);
Có 30% số test khác với 30% số điểm có m,n≤30 và cij không vượt quá 109;
Có 40% số test còn lại với 40% số điểm có m,n≤300 và cij không vượt quá 109.
Nguồn: 3D '1920