L-Strike Combo

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Gamer Alex đang chơi một game RPG có bản đồ dungeon dạng lưới ~n \times m~. Mỗi ô chứa một monster với điểm sức mạnh là số nguyên dương. Nhân vật của Alex có skill đặc biệt L-Strike Combo với quy tắc:

  • Chỉ có thể di chuyển theo một hướng (ngang hoặc dọc) ban đầu
  • Nếu có rẽ, sau khi rẽ thì đường đi sẽ chỉ được đi theo chiều sau khi rẽ.
  • Chỉ được rẽ một lần duy nhất
  • Không được quay lại ô đã đi qua.

Ví dụ:

  • Một đường đi chỉ đi thẳng ngang hoặc thẳng dọc là hợp lệ.

  • Một đường đi ngang rồi rẽ dọc, hoặc đi dọc rồi rẽ ngang cũng hợp lệ.

  • Một đường đi có hai lần rẽ hoặc quay lại ô cũ là không hợp lệ.

Combo cho phép người chơi chọn bất kì một nơi bắt đầu và nơi kết thúc, miễn ta có thể đi từ nơi bắt đầu đến nơi kết thúc một cách hợp lệ theo quy tắc của skill. Điểm Damage được tính bằng tích điểm sức mạnh của tất cả monster trên đường đi.

Alex rất thích số ~0~ vì nó tượng trưng cho sự hoàn hảo và cân bằng, do đó Alex muốn tìm combo có số chữ số ~0~ tận cùng nhiều nhất trong điểm Damage để khoe với bạn bè.

Yêu cầu: Cho bản đồ dungeon, hãy tìm số lượng chữ số ~0~ tận cùng lớn nhất có thể có trong điểm Damage của một skil L-Strike combo để Alex có thể khoe với bạn bè.

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, m~ ~(1 \le n, m \le 10^3)~

~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên dương ~a_{i,j}~ ~(1 \le a_{i,j} \le 10^3)~

Output

Một dòng duy nhất là số lượng số ~0~ lớn nhất trong damage của một skill L-Strike combo có thể có

Subtask

Subtask Điểm Ràng buộc
~1~ ~20~ ~n \le 10~
~2~ ~20~ ~n \le 100~
~3~ ~60~ không có giới hạn gì thêm

Sample Input 1

2 2
5 2
4 3

Sample Output 1

1

Sample Input 2

5 5
29 13 5 7 120
1 1 60 21 19
1 1 3 2 21
20 11 4 5 6
22 8 9 2 3

Sample Output 2

3

Giải thích

  • Ở ví dụ đầu:
5 2
4 3
  • Ở ví dụ thứ 2:
29 13 5 7 120
1 1 60 21 19
1 1 3 2 21
20 11 4 5 6
22 8 9 2 3

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.