Connection Status:
Competition Arena > EnergyGameOnGrid

EnergyGameOnGrid

TCO 2014 Wildcard · 2014-03-26 · by K.A.D.R

TCO 2014 Wildcard · 2014-03-26 · by K.A.D.R · Graph Theory, Search
Class Name: EnergyGameOnGrid
Return Type: String
Method Name: isReachable
Arg Types: (int, int, vector<int>, int, int, int, int, int)
Problem Statement

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 < N; i++){
	for(j = 0; j < M; j++){
		grid[i][j] = Empty;
	}
}

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

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

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
0)
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

1)
2
2
{0,0,1,1,2147000000}
0
0
1
1
1
Returns: "Impossible"

Here the grid looks like this: 01 10

2)
5
4
{0,0,3,3,1500000000,2,2,4,3,12857676,0,2,4,3,1500000000}
0
1
3
3
3
Returns: "Possible"

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

3)
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.

4)
2000
2000
{1000,1000,1001,1001,0}
386
111
1948
635
2000
Returns: "Possible"

Here the grid is completely free of walls.

16)
2000
2000
{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}
1075
446
364
1216
72
Returns: "Impossible"

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

Submissions are judged against all 186 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EnergyGameOnGrid with a public method string isReachable(int N, int M, vector<int> p, int r1, int c1, int r2, int c2, int E) · 186 test cases · 2 s / 256 MB per case

Submitting as anonymous