# SkyForce

ptrdung
plain_text
2 months ago
8.3 kB
1
Indexable
Never
```There is an airplane game which to avoid enemies and gather coins.

The game's map has height is N and width is 5 (5 ≤ N ≤ 12), but due to the limit of the screen, the gaming zone is 5x5. Below the gaming zone, there is control zone, which is one line at the bottom of the screen where airplane move.

At the start of game, the airplane locates at center point of control zone.

Game rule :

- Movement of airplane can be one of 3 options : left - right - stay at current column

- In each turn, after airplane move, game map will move down one line

- There is an option to use Bomb : bomb can be used to destroy all enemies in gaming zone, after used, all enemies will disappear and all coins will remain in the map. Bomb can be used only one.

- When airplane meets a cell with coin, number of coins collected will increase by 1, if it meet an enemy, number of coins will decrease by 1. If number of coins < 0 -> Game Over.

Given the map Nx5 with C is value of each cell (0: nothing, 1: coin, 2:enemy), find out the maximum amount of coins can be achieved after finishing the game. If the game can not be finished (Game Over), return -1.

[Input]

The first line is the total number of test cases T ( T <= 50)

The first line of each test case contain N, which is the height of the map, then the N lines following descript the map's data.

[Output]

The maximum number of coins that can be collected after finishing the game.

If the game can not be finished, print -1.

Input

2

5

1 1 0 0 0

1 2 2 2 1

1 1 2 2 1

2 2 2 1 2

2 2 0 2 0

8

2 0 2 0 2

1 0 1 2 0

0 0 0 2 1

2 0 2 0 1

1 2 1 2 0

0 2 2 0 2

2 1 1 2 2

0 2 1 2 0

Output

Case #1

3

Case #2

4

#include <iostream>

using namespace std;

int n, map[13][5]; // 0: nothing , 1 coin, 2 enermy, 3 nothing after bomb dissapear
int dy[3] = {-1,0,1};
int flag;
int ans;

void bomb(int x)
{
for(int i = x-1; i >= 0 && i >= x-5; i--)
for(int j = 0; j < 5; j++)
if(map[i][j] == 2) map[i][j] = 3;
}

void bombReset()
{
for(int i = 0; i < n; i++)
for(int j = 0; j < 5; j++)
if(map[i][j] == 3) map[i][j] = 2;
}

void BT(int x, int y, int score)
{
if(x < n && score < 0)
{
score = -1;
return;
}
if(x == 0)
{
if(ans < score) ans = score;
return;
}
for(int i = 0; i < 4; i++)
{
if(i == 3)
{
if(flag == 0)
{
flag = 1;
bomb(x);
BT(x, y, score);
bombReset();
flag = 0;
}
}else
{
int yNext = y + dy[i];
if(yNext >= 0 && yNext < 5)
{
if(map[x-1][yNext] == 0 || map[x-1][yNext] == 3) BT(x-1, yNext, score);
if(map[x-1][yNext] == 1) BT(x-1, yNext, score+1);
if(map[x-1][yNext] == 2) BT(x-1, yNext, score-1);
}
}
}
}

int main()
{
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++)
{
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < 5; j++)
cin >> map[i][j];
ans = -1;
flag = 0;
BT(n, 2, 0);
cout << "Case #" << tc << endl << ans << endl;
}

return 0;
}

50
7
2 1 2 2 0
0 2 2 0 0
2 0 2 1 0
0 0 2 1 2
0 2 1 0 2
1 2 1 0 2
1 1 2 0 2
5
0 0 1 0 0
1 2 1 0 2
2 2 0 0 1
2 1 2 1 0
2 1 2 0 2
9
2 2 2 2 2
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 2 2 0
6
2 2 2 2 2
0 0 0 0 0
0 0 2 0 0
2 0 0 0 2
0 0 0 0 0
1 2 2 2 1
10
1 0 1 0 1
2 2 2 2 1
0 2 2 0 2
2 0 2 1 1
2 0 2 2 0
0 2 2 1 1
2 0 2 1 2
2 1 1 2 2
1 1 2 2 2
2 1 0 1 0
9
2 0 1 1 1
0 1 0 1 2
0 1 0 2 2
0 0 0 2 1
2 0 1 0 1
0 0 2 0 2
1 0 0 2 2
2 0 0 1 1
2 0 0 0 0
7
1 2 0 1 0
0 1 2 1 2
2 0 0 0 0
2 2 1 1 2
0 0 2 0 2
0 1 0 1 1
2 1 2 0 2
8
1 2 1 1 2
1 1 2 0 0
2 1 1 2 1
1 2 1 2 0
0 0 2 2 1
1 0 2 0 0
1 2 1 2 0
0 0 2 0 1
12
2 2 2 1 0
1 2 0 0 2
1 0 1 0 1
2 1 2 1 1
1 2 2 1 2
2 2 1 0 1
2 0 1 1 0
0 2 1 0 2
1 2 2 1 2
2 2 1 2 0
1 0 2 0 1
0 0 0 1 0
12
0 0 2 2 0
2 0 0 1 2
0 1 1 2 2
0 0 1 0 2
0 2 2 0 2
1 0 2 2 0
2 2 2 2 1
1 0 1 2 2
2 1 0 1 1
1 0 1 1 0
2 2 1 1 2
0 0 1 0 2
5
1 1 0 0 0
1 2 2 2 1
1 1 2 2 1
2 2 2 1 2
2 2 0 2 0
12
2 1 2 2 2
0 2 2 1 0
0 0 1 0 1
0 1 0 2 0
2 0 0 0 0
0 1 1 0 1
0 1 0 2 2
1 1 0 2 2
2 2 1 2 2
2 0 1 0 2
1 2 1 2 0
2 0 1 1 1
11
1 1 0 0 2
0 1 1 2 2
1 0 0 1 2
2 0 1 1 2
0 0 0 2 0
2 1 2 2 0
2 1 0 2 0
1 1 2 2 1
1 2 0 0 0
2 1 0 0 2
0 0 0 2 1
8
0 0 2 2 2
2 1 1 2 2
2 0 1 1 1
1 1 2 0 0
0 0 2 0 1
0 2 0 0 1
1 1 1 2 0
0 2 0 1 2
9
1 0 0 0 0
2 2 1 1 2
0 1 1 0 0
1 2 0 2 0
1 1 1 0 0
2 1 1 0 1
0 0 1 1 1
2 1 0 0 0
0 1 2 2 1
10
2 2 2 2 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 2 2 0
12
1 0 1 0 1
1 1 1 0 1
0 2 0 2 0
2 0 1 0 0
0 1 2 1 0
1 2 0 1 0
0 1 1 0 2
0 1 1 1 1
0 2 0 1 0
0 0 0 1 2
1 0 0 2 2
0 0 2 0 2
12
0 2 2 0 2
0 2 0 0 0
2 0 1 2 0
0 1 1 2 1
1 2 2 2 0
1 2 1 1 2
2 0 2 1 2
2 1 1 1 0
1 0 0 1 1
2 1 0 1 2
2 1 0 1 1
1 0 2 2 0
9
0 1 1 1 1
1 0 2 0 2
2 2 2 2 1
1 0 0 0 2
1 0 2 2 1
2 1 0 1 2
1 1 0 2 1
2 2 0 0 1
1 1 0 2 0
9
1 1 0 2 0
2 2 0 2 0
1 1 0 1 0
2 0 1 1 0
1 0 1 1 2
0 0 2 1 0
2 0 2 2 1
2 0 1 1 2
2 0 2 0 0
8
2 1 1 1 0
2 1 2 2 1
0 1 0 0 2
0 1 1 0 1
2 0 0 0 2
2 0 1 1 1
0 0 1 1 0
1 1 0 0 0
10
2 0 2 2 2
0 1 0 2 1
0 0 2 1 1
1 0 1 0 1
2 0 0 0 2
0 2 2 0 2
1 1 0 2 2
0 0 1 0 1
1 1 2 0 2
0 1 0 2 0
8
1 2 1 1 1
2 1 2 1 1
1 2 0 2 2
2 0 1 0 0
1 1 2 2 0
1 0 1 2 1
1 2 0 1 2
1 2 0 0 1
10
2 1 0 0 2
2 0 0 0 1
2 1 2 2 0
0 1 0 0 1
0 2 2 2 1
2 1 0 0 0
2 0 2 1 2
2 1 2 1 2
2 0 2 0 2
1 0 2 2 1
8
2 0 2 0 2
1 0 1 2 0
0 0 0 2 1
2 0 2 0 1
1 2 1 2 0
0 2 2 0 2
2 1 1 2 2
0 2 1 2 0
8
1 1 1 2 2
1 1 1 1 2
2 1 2 2 0
2 0 0 2 2
1 0 0 0 2
1 0 2 0 2
2 0 2 0 2
0 2 0 0 1
9
1 2 2 0 2
2 0 2 1 2
1 0 1 2 1
1 0 2 1 1
2 0 1 2 1
1 2 2 0 2
0 2 0 1 0
1 0 2 2 2
2 0 2 0 1
12
1 0 1 2 1
0 2 2 1 0
0 0 2 1 0
1 1 1 1 1
2 0 2 0 0
1 2 1 2 1
0 0 0 1 2
1 1 1 1 0
2 0 2 2 1
0 0 0 2 0
1 0 2 2 2
0 1 1 1 0
8
1 0 0 2 2
2 0 1 1 0
0 0 1 2 2
1 0 1 0 0
1 1 1 0 2
1 0 1 2 0
2 2 0 2 1
0 1 2 1 0
8
2 0 0 0 0
0 0 0 1 0
2 1 0 1 2
1 2 0 0 2
1 2 1 0 1
0 2 1 1 2
1 2 0 2 2
1 1 2 2 0
7
1 0 2 0 1
0 0 1 2 1
2 1 1 2 2
1 0 2 0 1
2 2 1 2 2
0 0 1 0 2
0 0 2 2 0
9
2 2 2 0 1
2 2 0 2 1
1 0 0 2 1
2 2 2 0 1
2 2 0 0 2
1 0 2 1 1
1 2 1 1 2
0 0 2 2 0
2 0 0 0 2
8
1 1 1 0 1
0 1 1 1 2
2 1 1 0 1
2 2 0 0 2
1 1 0 0 2
2 2 0 2 1
2 0 1 1 2
2 0 1 0 0
8
0 2 2 1 1
1 2 1 0 1
0 0 2 2 0
1 0 1 1 1
0 2 0 0 1
0 2 0 1 2
1 0 0 1 1
1 0 2 0 0
12
2 2 2 2 2
2 2 2 1 2
2 1 1 0 0
2 2 2 1 2
2 2 1 0 2
0 0 0 1 1
1 0 0 1 1
0 0 1 1 0
0 1 0 2 1
1 1 1 0 2
0 0 2 1 0
2 0 2 2 2
10
1 0 2 1 2
1 2 1 0 1
1 0 0 1 1
1 1 1 1 1
1 2 1 0 0
1 1 1 2 2
0 1 2 1 1
0 0 0 1 2
1 2 0 1 2
2 1 0 1 0
11
1 0 0 0 2
2 2 0 1 2
1 2 1 0 2
1 1 0 1 0
0 2 1 0 1
2 0 0 1 2
1 0 1 0 2
0 1 1 2 0
1 0 0 0 0
0 2 0 2 1
2 2 0 2 1
9
1 0 1 2 2
2 2 1 1 1
0 0 0 1 0
0 0 0 2 0
2 1 0 1 0
2 0 2 2 1
2 2 1 1 2
1 0 0 1 1
1 1 1 1 2
9
0 0 1 2 2
0 2 0 1 0
2 0 2 2 1
2 2 2 1 1
2 2 2 1 0
0 1 0 2 1
2 1 1 1 1
0 1 0 2 1
2 1 2 2 1
7
0 1 0 1 2
2 0 1 2 1
0 2 2 1 1
1 1 0 0 0
1 0 1 1 1
1 0 2 1 1
2 0 2 0 2
12
0 1 1 0 1
0 2 0 2 2
1 0 0 1 2
2 1 1 1 0
0 2 0 0 1
0 2 1 2 2
2 2 1 1 1
0 1 2 1 0
0 0 1 1 0
2 2 0 1 2
1 1 1 1 2
0 0 1 1 1
10
1 1 2 2 1
2 1 2 2 0
2 2 1 0 0
0 1 2 2 0
1 0 2 0 1
1 2 2 0 2
0 0 0 1 2
1 2 2 1 0
1 0 1 2 2
1 2 1 1 0
11
1 2 0 0 1
2 1 1 0 2
1 2 0 2 2
1 2 0 1 1
2 0 2 2 0
1 2 1 2 1
1 0 0 0 1
0 0 1 1 2
1 0 1 0 2
1 1 2 0 2
2 0 0 2 2
9
0 1 2 2 2
2 2 2 1 1
2 2 1 1 1
1 2 2 2 1
2 1 2 2 2
0 1 2 2 0
0 0 0 0 0
2 1 1 0 1
1 2 2 1 1
11
1 2 1 0 1
0 2 1 1 2
1 0 0 1 1
2 2 0 0 1
1 0 0 2 2
1 2 1 2 0
1 1 0 0 2
2 0 1 2 2
1 2 2 1 1
1 1 1 2 1
2 1 0 0 0
8
1 2 1 2 1
1 1 0 0 2
2 2 2 2 1
1 1 0 0 2
1 2 1 1 2
0 1 1 1 2
0 0 0 1 0
1 2 2 1 0
8
1 0 1 1 1
1 0 2 0 0
2 2 0 1 2
1 0 0 0 2
0 2 0 1 2
2 1 2 0 1
2 2 2 2 0
1 2 2 1 2
8
1 0 2 1 0
0 2 1 0 2
2 0 0 0 1
0 0 2 2 0
1 2 1 0 2
0 1 1 1 1
1 2 1 2 1
2 0 0 1 2
9
1 2 1 0 2
2 2 2 1 1
2 1 1 2 1
1 2 1 0 2
1 2 1 1 0
1 1 1 2 2
0 1 0 2 0
0 0 0 0 0
1 2 0 0 1
8
2 2 0 0 1
2 1 2 2 1
0 0 0 1 1
0 2 1 1 0
0 2 2 1 1
1 0 0 0 2
2 1 2 2 1
1 1 2 0 0```