Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.7 kB
0
Indexable
Never
#include <iostream>
#define max(a, b) (a > b) ? a : b
using namespace std;
int T, N;
int maxA;
int arr[20][20];
int map[20][20];
bool bomb;

int X[3] = {-1, -1, -1};
int Y[3] = {-1, 0, 1};

void clearBomb(int row){
    for(int i = row - 1; i >= row - 5 && i >= 0; i--){
            for(int j = 0; j < 5; j++){
                if(arr[i][j] == 2){
                    arr[i][j] = 0;
                }
            }
    }
}
void back(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 5; j++){
            arr[i][j] = map[i][j];
        }
    }
}
void backtrack(int row, int col, int sum){
    if(row == 0){
        maxA = max(sum, maxA);
        return;
    }
    if(sum < 0) return;

    if(bomb == false){
        bomb = true;
        clearBomb(row);
        backtrack(row, col, sum);
        bomb = false;
        back();
    }
    for(int i = 0; i < 3; i++){
        int nr = row + X[i];
        int nc = col + Y[i];
        if(nr >= 0 && nr < N && nc >= 0 && nc < 5){
            int add = 0;
            if(arr[nr][nc] == 1){
                add += 1;
            }else if(arr[nr][nc] == 2){
                add -= 1;
            }
            backtrack(nr, nc, sum + add);
        }
    }
}

int main(){
    freopen("input.txt", "rt", stdin);
    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 >> arr[i][j];
                map[i][j] = arr[i][j];
            }
        }
        maxA = -1;
        bomb = false;
        backtrack(N, 2, 0);
        cout << "Case #" << tc << endl;
        cout << maxA << endl;
    }
    return 0;
}
Leave a Comment