EnergyGameOnGrid | Topcoder Archive

Problem Statement

Little Petya likes computer games a lot. He is currently playing the last level of a game. The level is a rectangular grid with N rows by M columns of cells. The cells have coordinates between (0,0) and (N-1,M-1), inclusive. Each cell is either empty or occupied by a wall. You will be given the layout of the level. (The precise format is specified at the end of this statement.)

At the beginning of the game Petya's character appears in the cell (r1,c1) with E units of energy. His task is to find a sequence of valid actions (described below) that takes his character from the cell (r1,c1) to the cell (r2,c2).

The rules for the actions are as follows: In each action, Petya can do one of two things:

If his character's energy is still positive, he can decrease it by 1.
He can make the character jump by exactly K cells in one of the four cardinal directions, where K is the character's current energy. The target cell has to be on the board and it has to be free (not a wall). Note that the cells between the current cell and the target cell may contain walls. Also note that jumping does not decrease the character's energy.

Petya wins the game if he finds a finite sequence of actions that will bring his character to the desired destination cell.

You are given the grid in the format described below, Petya's character starting position, ending position and initial level of energy. Determine whether Petya can win the game or not. Return "Possible" (without quotes) if Petya can do that and "Impossible" otherwise.

In order to keep the input size small, the grid should be pseudo-randomly generated. You are given a int[] p. The following pseudocode describes how to obtain the configuration of the grid.

64bit_integer x = N + 2 * M + 3 * r1 + 4 * c1 + 5 * r2 + 6 * c2;

for(i = 0; i &lt; N; i++){
	for(j = 0; j &lt; M; j++){
		grid[i][j] = Empty;
	}
}

for(i = 0; i &lt; length(p); i += 5){
	for(j = p[i]; j &lt;= p[i + 2]; j++){
		for(k = p[i + 1]; k &lt;= p[i + 3]; k++){
			x = (x * 1103515245 + 12345) % (64bit_integer)2147483648;
			if(x &lt; p[i + 4]){
				grid[j][k] = Wall;
			} else {
				grid[j][k] = Empty;
			}
		}
	}
}

grid[r1][c1] = Empty;
grid[r2][c2] = Empty;

Definition

Class:: EnergyGameOnGrid
Method:: isReachable
Parameters:: int, int, int[], int, int, int, int, int
Returns:: String
Method signature:: String isReachable(int N, int M, int[] p, int r1, int c1, int r2, int c2, int E)
(be sure your method is public)

Constraints

N and M will be between 1 and 2000, inclusive.
p will contain between 1 and 50 elements, inclusive.
The number of elements in p will be divisible by 5.
p[i] will be between 0 and N-1, inclusive for all valid i such that i mod 5 = 0.
p[i] will be between 0 and M-1, inclusive for all valid i such that i mod 5 = 1.
p[i] will be between p[i-2] and N-1, inclusive for all valid i such that i mod 5 = 2.
p[i] will be between p[i-2] and M-1, inclusive for all valid i such that i mod 5 = 3.
p[i] will be between 0 and 2,147,483,647, inclusive for all valid i such that i mod 5 = 4.
r1 and r2 will be between 0 and N-1, inclusive.
c1 and c2 will be between 0 and M-1, inclusive.
E will be between 1 and max(N, M), inclusive.

Examples

```
2
```
```
2
```
```
{1,0,1,0,2140000000}
```
```
0
```
```
0
```
```
1
```
```
1
```
```
1
```
```
Returns: "Possible"
```
In this case the grid looks like this ('0' stands for empty cells and '1' stands for cells occupied by walls): 00 10

{0,0,1,1,2147000000}

Returns: "Impossible"

Here the grid looks like this: 01 10

{0,0,3,3,1500000000,2,2,4,3,12857676,0,2,4,3,1500000000}

Returns: "Possible"

Here is how the grid looks like in this test case: 1001 1110 1111 1010 0001

```
3
```
```
10
```
```
{0,0,0,9,2147000000,0,4,2,9,2147000000,1,0,1,9,2147000001}
```
```
0
```
```
0
```
```
2
```
```
9
```
```
10
```
```
Returns: "Impossible"
```
Here is how the grid looks like in this test case: 0111111111 1111111111 0000111110 It's impossible to reach the target cell with any initial amount of energy.

{1000,1000,1001,1001,0}

Returns: "Possible"

Here the grid is completely free of walls.

{0,0,1999,1999,2147319343,804,426,1187,1358,1501333603,900,774,1543,1815,745495001,334,301,1285,863,1797586332,500,280,1764,343,698919580,
320,17,906,607,660127261,194,1364,1007,1693,1166180009,446,1365,1403,1465,204638230,197,1283,421,1486,418539195,508,322,1443,1819,1056189843}

Returns: "Impossible"

In this test case we need at least 73 units of energy to reach the target cell.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.