Description
Koying is rich and, in an attempt to address the issue of the bumpy road (崎嶇不平的道路) in Hsinchu, has bought a road roller.
However, he realized after the purchase that he didn't have a driver's license.
As a temporary solution, he has decided to write a program to simulate how the road roller should move. His program simulates the following environment:
There is a grid of N × M cells, representing the map of Hsinchu City. Each cell has a bumpy value (崎嶇值).
A higher bumpy value means a more bumpy, and a bumpy value of 0 represents a flat (平整的) area.
Whenever the road roller passes over a cell, the ground becomes flattened, and the cell's bumpy value is set to 0.
Koying's movement rules are as follows:
- Koying starts from the top-left corner of Hsinchu City, at coordinates (1, 1).
- Koying will not drive outside the boundaries of Hsinchu City, which range from (1, 1) to (N, M).
- Koying will choose the moving direction first.
Let X be the neighboring cell in one of the four directions (up, down, left, right) with the highest bumpy value and has not been flattened (bumpy value > 0). Koying will choose the direction of X as his moving direction. - Koying will start driving the road roller to the direction of X.cKoying will stop until he is on a cell with a higher bumpy value than X or he is on the last cell in that direction. When Koying stops on a cell, he will flatten it. After flattening the cell he stopped on, he will find a new direction to move on (go to step 3).
(Hint: in this step, Koying won't stop when he reaches a cell with a bumpy value of 0, or all his surrounding cells' bumpy values are 0.) - Koying will stop rolling the road when all four neighboring directions around Koying have been flattened.
Your task is calculating the total sum of flattened ground's bumpy values.
Note that if a cell is passed over multiple times, its bumpy value should not be accumulated more than once since each area can only be flattened once.
If Koying manages to flatten all the roads in Hsinchu City, you should output "Road Roller Da!!".
As Koying is currently occupied with helping the power plant at National Tsing Hua University generate electricity, and his absence might lead to a power outage, he has requested you finish this program so that he can focus on power generation.
No recursion is required in this problem! :)
Input
The first line contains two positive integers, N and M, representing the size of the grid.
Following that, there are N lines, each containing M positive integers Ai, j, indicating the bumpy value of the grid cell at row i and column j.
Constraints:
- 1 ≤ N, M ≤ 100
- 1 ≤ Ai, j ≤ 10,000
- It is guaranteed that no two grid cells have the same bumpy value.
Output
In the first line, please output a positive integer, representing the total sum of flattened ground's bumpy values.
If the road roller manages to pass over every grid cell, please output "Road Roller Da!!" (without quotation marks) on the second line.
Remember to print a ‘\n’ at the end of the output.
Sample IO Description
Sample I/O 2:
Hsinchu City
Koying starts from the top-left corner of Hsinchu City.
right(39) > down(37), so drive the road roller to right, until he met a cell with a higher bumpy value than 39. (but there is no bumpy value greater than 39, so koying stop at the last cell in this direction.)
go down, until he met a cell with a higher bumpy value than 3. (so Koying will stop at 6.)
down(49) > left(17), so koying go down until he met a cell with a higher bumpy value than 49. (but there is no bumpy value greater than 49, so koying stop at the last cell in this direction.)
go left, until he met a cell with a higher bumpy value than 32. (so Koying will stop at 38.)
up(36) > left(31), so koying go up until he met a cell with a higher bumpy value than 36. (but there is no bumpy value greater than 36, so koying stop at the last cell in this direction.)
four neighboring directions around Koying have been flattened, so the simuates is stop.
the total sum of flattened ground's bumpy values is 18 + 39 + 14 + 13 + 25 + 3 + 6 + 49 + 41 + 32 + 1 + 38 + 36 + 27 + 7 = 349 .