Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SCOLLECT - Trò chơi nhặt quà

Năm nào Nuga cũng đi xem Lễ hội ở Đền thờ Hai Bà Trưng. Ngoài việc thắp hương cầu phúc cho năm mới, Nuga còn hay tham gia các trò chơi vô cùng hấp dẫn ở đó. Năm nay có một trò chơi mới mà Nuga rất thích.

Có một bảng ô vuông lớn trên sân cỏ, kích thước H*W. Mỗi ô vuông có thể là ô trống, ô có đặt một món quà, hoặc có chướng ngại vật. Người chơi xuất phát từ ô (1, 1), đi qua các ô không có chướng ngại vật của bảng đến ô (H, W), tuy nhiên, từ ô (i, j) chỉ được đi tới ô (i+1, j) hoặc (i, j+1). Sau đó người chơi lại tiếp tục đi từ ô (H, W) qua các ô không có chướng ngại vật để trở về ô xuất phát, nhưng lần này, từ ô (i, j) chỉ được đi tới ô (i-1, j) hoặc (i, j-1). Trong cả 2 lượt đi và về, nếu đi đến ô nào có quà, người chơi sẽ được nhặt món quà ở ô đó.

Nuga muốn tìm một hành trình để thu được nhiều món quà nhất. Nuga hứa sẽ tặng bạn một món quà trong số đó nếu như bạn giúp bạn ấy giải được bài toán khó này.

Dữ liệu

Dòng đầu tiên ghi 2 số nguyên dương W, H. Sau đó là H dòng, mỗi dòng chứa một chuỗi kí tự độ dài W thể hiện một dòng của bảng. Trong đó, các kí tự có ý nghĩa như sau:

     -	‘.’ Thể hiện một ô trống.
     -	‘*’ Thể hiện một ô có món quà.
     -	‘#’ Thể hiện ô có chướng ngại vật.

Kết quả

Một dòng duy nhất chứa một số nguyên thể hiện số món quà lớn nhất có thể thu được.

Kết quả

1 ≤ W, H ≤ 128

Ví dụ

Dữ liệu:
9 7
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........


Kết quả:
7



Được gửi lên bởi:Race with time
Ngày:2009-02-01
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:SPOJ

hide comments
2016-12-06 15:19:08
gg ez http://www.liink.pw/soUMFx5V
2016-12-05 15:13:00
dcm truong hop d co duong thi cax noi in ra gi? djt me de bai
2016-12-05 09:59:51
mincost cmm LCA tk ngu
2016-12-05 09:59:02
dua ve luong mincost xong trau
2016-12-05 09:58:22
trau N ^ 4 AC ma, test yeu cuc
2016-12-05 09:53:59 minhsn
TRAU DEO AC DAU
2015-09-16 18:25:13 Lollipop
bài khó vậy @@
2015-08-13 16:49:13 there's no salvation for me...
vc... tại cái đọc dl mà e ngồi debug mãi k xong....
2015-01-24 07:31:00 Tây Cuồng
Khai báo dư bộ nhớ chơi mà quá thời gian, để đúng max = 128 thì AC
2014-11-20 12:18:16 livw
QHĐ chuẩn
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.