findMaxTreasure
Hòn đảo kho báu NOWHERE có dạng một hình chữ nhật board kích thước MxN. Mỗi ô (i, j) của một hòn đảo chứa một số nguyên dương x thể hiện lượng kho báu nằm trong ô đó. Một hôm Đăng chế tạo ra một con Robot với mong muốn lấy được nhiều kho báu nhất có thể về cho mình. Con Robot của Đăng hoạt động như sau:
- Robot không đi được ra ngoài hoàn đảo. Nói cách khác nếu Robot đang đứng ở ô
(u, v)thì0 <= u < M,0 <= v < N - Nếu Robot đang đứng ở ô
(u, v)thì trong lần di chuyển tiếp theo, Robot có thể đến1trong4ô:(u+1, v).(u-1, v).(u, v+1).(u, v-1).
- Trong một lần di chuyển thì Robot chỉ có thể đi được đến ô có nhiều kho báu hơn ô hiện tại nó đang đứng. Hay nói cách khác gọi ô
(u, v)là ô Robot hiện tại đang đứng và có lượng kho báu làxthì ô tiếp theo Robot di chuyển đến là(p, q)có lượng kho báu làythìy >= x - Nếu đến một ô mà Robot không thể đi được nữa thì Đăng sẽ thu hồi Robot về và tính lượng kho báu mà Robot thu thập được
Nhiệm vụ của bạn là giúp Đăng tìm ô bắt đầu để đặt Robot và đường đi tốt nhất để Robot có thể lấy nhiều kho báu nhất có thể. Bài toán yêu cầu trả vể lượng kho báu lớn nhất mà Robot lấy được.
Chú ý: Đặt Robot tại ô bắt đầu là (u, v) thì lượng kho báu ở ô (u,v) vẫn được tính vào kết quả.
Ví dụ:
- Với
Board = [[1,8,7,9,1],[1,7,6,10,2],[1,7,1,3,9],[6,1,3,1,1],[1,1,1,1,7]]thìfindMaxWay(Board) = 33.
Ta có bản đồ kho báu ban đầu sẽ có dạng
Ta sẽ đặt Robot ở ô1 8 791 1 7 6102 1 7 13 9 6 1 3 1 1 1 1 1 1 7 (2, 2)và di chuyển theo lộ trình như sau:(2, 2) -> (1, 2) -> (0, 2) -> (0, 3) -> (1, 3)
thì lượng kho báu ta nhận được là1 + 6 + 7 + 9 + 10 = 33
Đầu ra/Đầu vào
- [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java/C#, 4s với Python,Js, Go
- [Đầu vào]: matrix.integers Board
1 <= Board.size() <= 7001 <= Board[i].size() <= 700 với 0 <= i < Board.size()1 <= Board[i][j] <= 100 với 0 <= i < Board.size() và 0 <= j < Board[i].size() - [Đầu ra]: integer
Lượng kho báu nhiều nhất mà Robot có thể thu thập được
Post Comment