GDKOI 2016 Day2 T1 염색대전

T1 염색대전

점마다 검은색과 흰색 두 가지 상태가 있는 N*M의 격자 그림을 보여 줍니다.A, B 두 사람이 번갈아 조작하고 A가 먼저 한다.매번 조작할 때마다 흰 점을 검은 점으로 염색할 수 있다.만약 이번 염색에 새로운 간단한 검은색 정사각형(즉 가장 작은 정사각형, 네 개의 정점이 모두 검은색)이 생겼다면 그 점수를 획득하고 한 번 더 염색을 장려한다.두 사람 모두 최우선 전략에서 A의 득점-B의 득점의 값을 구한다.
단순 바둑.바둑만 할 줄 알면 할 줄 안다.분명히 A는 답을 크게 만들고, B는 답을 작게 만들려고 한다.귀속할 때 현재의 상태와 누가 조작했는지 기록하고 직접 검색하면 된다.기억화에 주의하세요.

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define inf 0x7fffffff
#define N 8
#define M 2100005
using namespace std;
int a[N][N],c[N][N],f[M],mi[N][N],n,m,t,p;
int pd(int x,int y) {
    return a[x][y]&&a[x+1][y]&&a[x][y+1]&&a[x+1][y+1];
}
int max(int x,int y) {if (x>y) return x;else return y;}
int dfs(int x,int id) {
    int ret=-inf,z;
    if (f[id+x*p]!=t) return f[id+x*p];
    fo(i,1,n)
        fo(j,1,m)
            if (!(id&mi[i][j])) {
                z=0;a[i][j]=1;
                if (pd(i,j)) z+=c[i][j];if (pd(i-1,j)) z+=c[i-1][j];
                if (pd(i,j-1)) z+=c[i][j-1];if (pd(i-1,j-1)) z+=c[i-1][j-1];
                if (z) ret=max(ret,z+dfs(x,id+mi[i][j]));
                else ret=max(ret,z-dfs(1-x,id+mi[i][j]));
                a[i][j]=0;
            }
    f[id+x*p]=ret;return ret;
}
int main() {
    scanf("%d%d",&n,&m);memset(f,43,sizeof(f));t=f[0];
    fo(i,1,n) fo(j,1,m) a[i][j]=1;p=1<<(n*m);
    int id=0;fo(i,1,n) fo(j,1,m) id=id*2+a[i][j];f[id]=0;
    id=1;fo(i,1,n) fo(j,1,m) id=id*2+a[i][j];f[id]=0;
    mi[n][m]=1;fd(i,m-1,1) mi[n][i]=mi[n][i+1]*2;
    fd(i,n-1,1) {
        mi[i][m]=mi[i+1][1]*2;
        fd(j,m-1,1) mi[i][j]=mi[i][j+1]*2;
    } 
    fo(i,1,n) fo(j,1,m) scanf("%d",&a[i][j]);
    id=0;fo(i,1,n) fo(j,1,m) id=id*2+a[i][j];
    fo(i,1,n-1) fo(j,1,m-1) scanf("%d",&c[i][j]);
    printf("%d",dfs(0,id));
}