J5. Connecting Territories
레이팅 미적용의견: 0
Ava is playing a strategic game on a grid of tiles. Each tile has an
associated cost. When the costs of the tiles are read from left to
right, starting with the first row, a repeating pattern of the first
\(M\) positive integers in increasing
order is revealed: \(1, 2, 3, \ldots, M, 1, 2, 3, \ldots, M, 1, 2, 3, \ldots\). In this pattern, \(M\) represents the maximum cost of a tile.
In the grid of tiles shown, \(M\) is
equal to \(5\).
Ava needs to purchase one tile in each row in order to make a
connecting path from the upper territory (above the first row of tiles)
to the lower territory (below the last row of tiles). The first tile
purchased must be in the first row. Each subsequently purchased tile
must share either an edge or a corner with the tile purchased
previously. In the grid of tiles shown, the cost of Ava’s connecting
path is \(9\).
Given a grid of tiles, your job is to determine the minimum cost of a
connecting path between the upper and lower territories.
\(M \leq 100\,000\)
The first line of input contains a positive integer, \(R\), representing the number of rows in the
grid. The second line contains a positive integer, \(C\), representing the number of columns in
the grid. The third line contains a positive integer, \(M\) where \(M \leq 100\,000\), representing the maximum cost of a tile.
Output the positive integer, \(P\),
which is the minimum cost of a connecting path between the upper and
lower territories.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | There are two rows and at most ten columns. — \(R=2\) and \(C \leq 10\) |
2 | 54점 | There are at most ten rows and at most ten columns. — \(R \leq 10\) and \(C \leq 10\) |
3 | 13점 | There are at most \(100\) rows and at most \(100\) columns. — \(R \leq 100\) and \(C \leq 100\) |
4 | 13점 | The grid may be very large. — \(R \leq 20\,000\) and \(C \leq 20\,000\) |
3
5
76The cost of each tile is shown. The sequence of tiles that Ava should
purchase to minimize the cost of a connecting path is highlighted in
green.
평가 및 의견
J5. Connecting Territories
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
J5. Connecting Territories