关键
跟炮兵阵地那道题目很像,先确定上面哪一行的状态,然后在确定下面这一行的状态,采用dp就可以枚举所有的状态
代码
#include <bits/stdc++.h>
using namespace std;
const int M=1005;
int a[M][M],f[M][2][2];
int n,m;
bool check(int p,int x,int y) {
for(int i=1;i<=m;i++)
if(a[p][i]!=a[p][i-1]&&a[p][i]!=a[p][i+1]&&a[p][i]!=(a[p-1][i]^x)&&a[p][i]!=(a[p+1][i]^y))return 0;
return 1;
}
//每一行只会有两种状态,上面和下面
int main() {
cin>>n>>m;
memset(a,-1,sizeof(a));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
memset(f,0x3f,sizeof(f));
f[1][0][0]=0;
f[1][0][1]=1;
for(int i=2;i<=n+1;i++)//现在这一样
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)//我的状态
for(int l=0;l<2;l++)//上下两行是什么状态
if(check(i-1,l^k,k^j))f[i][k][j]=min(f[i][k][j],f[i-1][l][k]+j);
int ans=min(f[n+1][0][0],f[n+1][1][0]);
if(ans>=n)ans=-1;
cout<<ans<<endl;
return 0;
}
//我这一行边,和上面两行变是没有区别的
标签:abc,--,memset,int,283,sizeof
From: https://www.cnblogs.com/basicecho/p/17003470.html