洛谷。
题目传送门。
某次校内模拟赛的 T1。
分析
注意到 \(n\le100\)，显然这是一道搜索题。考虑怎么来搜。
我们发现，四块小棋盘可以在左上、右上、左下、右下任意排列，那么构成大棋盘的总方案数就是 \(4!=24\) 种。这个数并不大，我们可以写四重循环来枚举它。对于枚举出来的每一种方案，我们都求出它的代价，然后取最优的。
接下来考虑我们得到一个构造好的大棋盘后，应该怎么求它的代价。容易想到从左上角开始广搜。维护一个队列，队列中的每个结点都有横纵坐标两个属性。每次判断当前结点的右（下）方是否还有不在队列中的结点；如果有，就将这个结点入队。同时，判断当前结点是否与左（上）方的结点同色；如果是，代价加一并将这个结点重新染色。
为确保分讨全面，我们要在广搜过一次后将左上角的颜色改变一次，再重新广搜，两次的结果取最小代价。
然后就做完了。有一点小细节，直接看代码吧。
代码
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#define inline __inline
#include<iostream>
#include<queue>
using namespace std;const int N=1e2+5;int n;bool a[5][N][N],mat[N<<1][N<<1],vis[N<<1][N<<1];namespace OIfast{char buf[1<<21],*p1,*p2,*top,buffer[1<<21];#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?0:*p1++)#define gc getchar()inline int read(){int n=0;char c=gc;while(!isdigit(c))c=gc;while(isdigit(c))n=(n<<3)+(n<<1)+(c^48),c=gc;return n;}inline bool get_(){char c=gc;while(!isdigit(c))c=gc;return c^48;}}using namespace OIfast;inline void input(){//输入有点长，单开一个函数。n=read();for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)a[1][i][j]=get_();for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)a[2][i][j]=get_();for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)a[3][i][j]=get_();for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)a[4][i][j]=get_();return ;
}inline void gz(int zs/*左上*/,int ys/*右上*/,int zx/*左下*/,int yx/*右下*/){//构造当前枚举到的大棋盘。for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)mat[i][j]=a[zs][i][j];for(int i=1;i<=n;++i)for(int j=n+1,k=1;j<=(n<<1);++j,++k)mat[i][j]=a[ys][i][k];for(int i=n+1,k=1;i<=(n<<1);++i,++k)for(int j=1;j<=n;++j)mat[i][j]=a[zx][k][j];for(int i=n+1,k=1;i<=(n<<1);++i,++k)for(int j=n+1,l=1;j<=(n<<1);++j,++l)mat[i][j]=a[yx][k][l];return ;
}#define pii pair<int,int>
#define x first
#define y secondinline int calc(){//对于已经构造好的大棋盘，求它的代价。for(int i=1;i<=(n<<1);++i)for(int j=1;j<=(n<<1);++j)vis[i][j]=0;int res=0;queue<pii >q;q.push(make_pair(1,1)),vis[1][1]=1;while(!q.empty()){pii cur=q.front();q.pop();int i=cur.x,j=cur.y;vis[i][j]=0;if(i>1)if(mat[i][j]==mat[i-1][j])++res,mat[i][j]^=1;if(j>1)if(mat[i][j]==mat[i][j-1])++res,mat[i][j]^=1;if(i<(n<<1)&&(!vis[i+1][j]))q.push(make_pair(i+1,j)),vis[i+1][j]=1;if(j<(n<<1)&&(!vis[i][j+1]))q.push(make_pair(i,j+1)),vis[i][j+1]=1;
// if(i<(n<<1)&&j+1<=(n<<1))q.push(make_pair(i+1,j+1));//走不到右下，这一行不能要。}return res;
}inline void getmn(int &a,int b){return a=(a<b?a:b),void();
}inline int solve(){int res=1e9;for(int i=1;i<=4;++i){//枚举左上、右上、左下、右下各放哪一块for(int j=1;j<=4;++j){if(i==j)continue ;for(int k=1;k<=4;++k){if(k==j||k==i)continue ;for(int l=1;l<=4;++l){if(l==k||l==j||l==i)continue ;gz(i,j,k,l)/*左上角不动的情况*/;getmn(res,calc());gz(i,j,k,l),mat[1][1]^=1/*左上角要动的情况*/;getmn(res,calc()+1/*注意，这个地方一定要加上 1，因为改变左上角的颜色本身也会产生贡献*/);}}}}return res;
}signed main(){input();return cout<<solve()<<"\n",0;
}