POND - Hồ Cá
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: a516ami_crush_tuyetni

Vì đã tán crush thành công nên lần này Ami sẽ viết đề. Mời các bạn đọc đề.

          Ami có một hồ súng. Hồ súng có thể biểu diễn đơn giản là một ma trận 2 chiều, có m hàng, n cột. Giao giữa hàng  i và cột j là ô (i,j). Ô (i,j) có thể có lá súng hoặc không.

          Crush Ami rất thích hái lá súng. Cô bảo rằng lá súng có thể chế biến thành nhiều món ăn rất ngon và tốt cho sức khỏe. Vì thế hằng ngày, cô đều ra hồ hái hoa. Crush Ami chỉ có thể di chuyển trong các ô có hoa súng. Từ một ô (i,j) có hoa, cô có thể di chuyển đến các ô kề cạnh (lên, xuống, phải, trái) nếu các ô đó có hoa súng và không nằm ngoài hồ. Và đương nhiên, Crush của Ami có thể di chuyển qua các ô cô đã hái hoa, nhưng sẽ không hái được thêm bông hoa nào từ các ô đó.

          Ami muốn trồng thêm 1 bông hoa súng vào một ô không có hoa. Vì thương Crush, cậu muốn sau khi trồng thêm một bông hoa,Crush có thể hái được nhiều hoa hơn. Vì thế, cậu cần các bạn tính toán xem, nếu Ami trồng hoa súng tại một ô đang không có hoa, thì nếu bắt đầu hái hoa từ ô đó, Crush Ami có thể hái được tối đa bao nhiêu bông hoa.

Dữ liệu vào

Dòng đầu chứa 2 số nguyên m và n (m , n <= 2*1000) lần lượt là số hàng và số cột biểu diễn hồ súng.

Tiếp theo là m dòng, mỗi dòng chứa n kí tự ‘*’ nếu ô đó không có hoa và ‘.’ trong trường hợp có hoa.

Dữ liệu ra

Gồm m dòng, mỗi dòng gồm n kí tự hoặc chữ số.

Là kí tự ‘.’ Nếu tại đó là một ô có hoa.

Trong trường hợp ô không chứa hoa, in ra số hoa lớn nhất mà Crush Ami có thể hái được nếu Ami trồng tại đó một bông hoa và Crush Ami bắt đầu hái hoa tại đấy SAU KHI ĐÃ CHIA DƯ CHO 10.

Ví dụ

Input

2 4

*.**

.**.

Output

3.22

.32.

 

Giải thích

Nếu Ami trồng hoa ở ô (1,1) Crush Ami có thể hái hoa ở các ô (1,1) ; (1,2) ; (2,1).

Nếu Ami trồng hoa ở ô (1,3) Crush Ami có thể hái hoa ở các ô (1,3) ; (2,3).

Nếu Ami trồng hoa ở ô (1,4) Crush Ami có thể hái hoa ở các ô (1,4) ; (2,4).

Nếu Ami trồng hoa ở ô (2,2) Crush Ami có thể hái hoa ở các ô (1,2) ; (2,1) ; (2,2).

Nếu Ami trồng hoa ở ô (2,3) Crush Ami có thể hái hoa ở các ô (2,3) ; (2,4).

Back to Top