###### tags: `I2P(I)Hu2022`
# 13679 - ZvP

> by schdoel

## Brief
On a nxn grid, place n starfruits such that no starfruit would get hit by bullets, and maximize the total points.

## Solution
n each row we try all the plans of placing a starfruit and simultaneously make sure no starfruit would attack another starfruit. Suppose we are placing the i-th star in the i-th row. We need to check all the stars in previous rows whether they would attack the starfruit for the plan you are trying now. We can use the similar strategy from 8 Queens problem to achieve checking.

## Reference Code

#include<stdio.h>
int n;
int grid[11][11]={0};
int col[11];
int digLeft[100];
int digRight[100];
long long max=-12345678912345ll;

void star(int row, long long sum){
    if(row==n){
        if(sum>max) max=sum; 
        return;
    }
    for(int collumn=0; collumn<n; collumn++){
        if(!col[collumn] && !digLeft[collumn+row] && !digRight[collumn-row+n]){
            col[collumn] = digLeft[collumn+row] = digRight[collumn-row+n] = 1;
            star(row+1, sum + grid[row][collumn]);
            col[collumn] = digLeft[collumn + row] = digRight[collumn - row + n] = 0;
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i=0; i<n;i++){
        for(int j=0; j<n; j++){
            scanf("%d", &grid[i][j]);
        }
    }
    star(0,0);
    if(max!=-12345678912345ll) printf("%lld\n", max);
    else printf("no solution\n");
    return 0;
}