已经优化了搜索顺序，先向右下搜索

//可放格子-最大匹配
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=210;
int g[N][N];
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};
PII match[N][N];
bool st[N][N];
int n;

bool check(int x,int y)
{
    return !g[x][y]&&x>=1&&x<=n&&y>=1&&y<=n;
}

bool find(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!check(a,b)) continue;
        if(st[a][b]) continue;
        st[a][b]=true;
        
        auto t=match[a][b];
        if(!t.x||find(t.x,t.y)) 
        {
            match[a][b]={x,y};
            return true;
        }
    }
    
    return false;
}

int main()
{
    scanf("%d",&n);
    int res=n*n;
    for(int i=1;i<=n;i++)
    {
        char s[N];
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)
        {
            if(s[j]=='0') g[i][j]=0;
            else g[i][j]=1,res--;
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]||(i+j)&1) continue;
            memset(st,0,sizeof st);
            if(find(i,j)) res--;
        }
    }
    
    printf("%d",res);
    
    return 0;
}