c_vj_Pebbles（基础题，预处理每一种状态）

在n*n的网格网格中取卵石，对于一个已经被取过的格子，它的相邻的八个方向都不能取，求总和最大的方案

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=16;
int n,ALL,g[N][N],p=1,f[2][1<<N],st[1<<N],m;
void init_st() {
    ALL=1<<n, m=0;
    for (int i=0; i<ALL; i++) if ((i&(i<<1))==0)
        st[m++]=i;
}
bool valid(int i, int j) {
    if ((i&j)!=0 || ((i<<1)&j)!=0 || (i&(j<<1))!=0) return false; //上下不能相邻，
    return true;
}
int get(int i, int mask) {
    int s=0;
    for (int j=0; j<n; j++) if (mask&(1<<j)) //第j位有1
        s+=g[i][n-j-1];
    return s;
}
int main() {
    while (n=0, scanf("%d", &g[0][n++])!=-1) {
        while (scanf("%d", &g[0][n++]), getchar()!='
');
        for (int i=1; i<n; i++)
        for (int j=0; j<n; j++)
            scanf("%d", &g[i][j]);
        init_st(), memset(f,0,sizeof f);
        for (int i=0; i<n; i++,p^=1)
        for (int j=0; j<m; j++) {
            int t=get(i, st[j]);
            for (int k=0; k<m; k++) if (valid(st[j], st[k]))
                f[p^1][j]=max(f[p^1][j], f[p][k]+t);
        }
        int ans=0;
        for (int j=0; j<m; j++) ans=max(ans, f[p][j]);
        printf("%d
",ans);
    }
    return 0;
}