#define _CRT_SECURE_NO_WARNINGS

#include <vector>

#include <iostream>

#include <utility>

#include <algorithm>

#include <cstdio>



#define NUMBER_FOR_Line 5

using namespace std;

vector < vector < int > > map;

int bomb_position;


int bomb_checking_adder(int depth, int position, int coin);

int dfs(int depth, int position, int coin)

{

coin=bomb_checking_adder(depth, position, coin);


if (coin <= -1)

return -1;


if (depth > 0)

{

if(position==0)

{ 

return max(dfs(depth - 1, position, coin), dfs(depth - 1, position + 1, coin));

}

else if(position == 4)

{

return max(dfs(depth - 1, position-1, coin), dfs(depth - 1, position , coin));

}

else 

{

int temp= max(dfs(depth - 1, position - 1, coin), dfs(depth - 1, position, coin));

return max(temp, dfs(depth - 1, position + 1, coin));

}

}

else

return coin;




}



int bomb_checking_adder(int depth, int position, int coin)

{


if (depth < bomb_position && depth > bomb_position -5 )

{

if (map[depth][position] == -1)

coin += 0;

else

coin += map[depth][position];

}

else

coin += map[depth][position];



return coin;

}





int main(void)

{

int test_case;


scanf("%d", &test_case);


for (int i = 0;i < test_case;i++)

{

int input_line_number;

scanf("%d", &input_line_number);

vector <int> one_line;

for (int j = 0;j < input_line_number;j++)

{

for (int k = 0; k < NUMBER_FOR_Line; k++)

{

int one_input;

scanf("%d", &one_input);

if (one_input == 2) one_input = -1;


one_line.push_back(one_input);

}

map.push_back(one_line);

one_line.clear();

}

int result = -999;


for (int bp = input_line_number;bp >= 5;bp--)

{

bomb_position = bp;

int temp_result = dfs(input_line_number-1, 2, 0);

result = max(result, temp_result);

printf("##%d %d\n", bp, temp_result);


}


printf("#%d %d\n", i + 1,result);

map.clear();


}


return 0;

}


이따위로 짜니 취업이 안되징 흑흑



이방법 외에는 모르겠당