騎士放置 Page435 最大獨立集

• 棋盤問題首先黑白染色
• 馬的哈密頓移動距離是3，必然是從白走到黑或者從黑走到白
• 這題折騰了倆小時，就因為遞迴那裡懶得寫int，直接用了個全域性變數，根本檢查不出來，人傻了

程式碼:

const int maxn=2e4+7;
const int INF=0x3f3f3f3f;
const ll INFF=1e18;
bool mark[120][120],vis[maxn];
int linker[maxn],n,m,t,x,y;
int xx[8]={1,1,-1,-1,2,2,-2,-2};
int yy[8]={2,-2,2,-2,1,-1,1,-1};
int f(int x,int y){return m*(x-1)+y;}
vector<int> V[maxn];
bool dfs(int x)
{
    repp(i,0,V[x].size())
    {
        int y=V[x][i];//這邊一定要加int，遞迴函數裡面的變數得定義
        if (vis[y])continue;
        vis[y]=true;
        if (!linker[y]||dfs(linker[y]))
        {
            linker[y]=x;
            return true;
        }
    }
    return false;
}
int count_()
{
    int ans=0;
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            if ((i+j)%2==0)
            {
                mem(vis,false);
                if (dfs(f(i,j)))ans++;
            }
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    rep(T,1,t)
    {
        scanf("%d%d",&x,&y);
        mark[x][y]=true;
    }
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            if (mark[i][j])continue;
            rep(k,0,7)
            {
                x=i+xx[k],y=j+yy[k];
                if (x<1||y<1||x>n||y>m||mark[x][y])continue;
                if ((i+j)%2==0)V[f(i,j)].pb(f(x,y));
            }
        }
    }
    W(n*m-t-count_());
    return 0;
}