Untitled

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.


Ex:
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
#define _CRT_SECURE_NO_WARNINGS
	
#include <stdio.h>

#define SIZE 15

int map[SIZE][SIZE];
int N;
int best;

void resetData() {
	int i, j;
	best = -1;
	for (i = 0; i < SIZE; ++i) {
		for (j = 0; j < 5; ++j) {
			map[i][j] = 0;
		}
	}
}

void move(int row, int col, int coin, int ignoreEnemy, bool have_bomb) {
	if (col < 0 || col > 4) return;

	if (row < 0) {
		if (best < coin) best = coin;
		return;
	}

	//process current cell
	if (map[row][col] == 1) {
		++coin;
	}
	else if (map[row][col] == 2 && ignoreEnemy <= 0) {
		if (coin > 0) --coin;
		else return;
	}

	//scroll down bombed area
	--ignoreEnemy;

	//move up
	move(row - 1, col, coin, ignoreEnemy, have_bomb);

	//use bomb and move up
	if (have_bomb) move(row - 1, col, coin, 5, false);

	//move top-left
	move(row - 1, col - 1, coin, ignoreEnemy, have_bomb);

	//use bomb and move top-left
	if (have_bomb) move(row - 1, col - 1, coin, 5, false);

	//move top-right
	move(row - 1, col + 1, coin, ignoreEnemy, have_bomb);

	//use bomb and move top-right
	if (have_bomb) move(row - 1, col + 1, coin, 5, false);
}

int main() {
#ifdef _CRT_SECURE_NO_WARNINGS
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int T, testcase;
	scanf("%d", &T);
	for (testcase = 1; testcase <= T; ++testcase) {
		scanf("%d", &N);
		resetData();
		int i, j, k;
		for (i = 0; i < N; ++i) {
			for (j = 0; j < 5; ++j) {
				scanf("%d", &map[i][j]);
			}
		}

		move(N, 2, 0, 0, true);

		printf("Case #%d\n%d\n", testcase, best);
	}
	return 0;
}