题解 | 取数游戏

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n, m;
int max = 0;
int a[10][10];
int valid(int row1[], int row2[]){
    for(int i = 0; i < m; i++){
        if(row1[i] == 1){
            if(i > 0 && row2[i-1] == 1)
                return 0;
            if(row2[i] == 1)
                return 0;
            if(i < m-1 && row2[i+1] == 1)
                return 0;
        }
    }
    return 1;
}
void dfs(int row, int cur_sum, int pre[]){
    if(row == n){
        if(cur_sum > max)
            max = cur_sum;
        return;
    }
    for(int i = 0; i < (1 << m); i++){
        if(i & (i << 1))
            continue;
        int cur_row[10] = { 0 };
        int row_sum = 0;

        for(int j = 0; j < m; j++){
            if(i & (1 << j)){
                cur_row[j] = 1;
                row_sum += a[row][j];
            }
        }
        if(row > 0 && !valid(cur_row, pre))
            continue;
        dfs(row+1, cur_sum+row_sum, cur_row);
    }
}
int main(void) {
    int t;
    scanf("%d", &t);

    while(t--){
        scanf("%d%d", &n, &m);

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                scanf("%d", &a[i][j]);
        
        max = 0;
        int start[10] = { 0 };
        dfs(0, 0, start);
        
        printf("%d\n", max);
    }
    return 0;
}