高性能网站建设进阶指南,手机论坛网站源码,吕梁网站定制,产品展示网站php源码给你一个n*n的01矩阵#xff0c;只能够将0变成1#xff0c;使得每个元素上下左右之和均是偶数#xff0c; 比如 0 0 0 0 1 0 1 0 01 0 1 0 0 0 0 1 0 一个转变了3步 多实例T 然后一个n#xff08;n15#xff09; 表示n*n的矩阵 …给你一个n*n的01矩阵只能够将0变成1使得每个元素上下左右之和均是偶数 比如 0 0 0 0 1 0 1 0 01 0 1 0 0 0 0 1 0 一个转变了3步 多实例T 然后一个nn15 表示n*n的矩阵 然后n*n个01整数 如果不能转换 输出-1 因为n*n的矩阵 而且n16所以状态压缩 遍历最上面的一层 #includecstdio
#includemath.h
#includecstring
#includealgorithm
#includeiostream
#includequeue
#includevector
#includemap
using namespace std;
#define INF 0x3f3f3f3f
#define N 20
int a[N][N],q[N][N],n;
int Q(int s)
{memset(q,0,sizeof(q));for(int i0;in;i){if(s(1i)) q[0][i]1;///直接换为1 else if(a[0][i]1) return INF;///如果已经是1 避免重复使用}for(int i1;in;i){for(int j0;jn;j){///要从第0层 开始往下推int sum0;///q[i-1][j]上左右的元素和if(i1) sumq[i-2][j];if(j0) sumq[i-1][j-1];if(jn-1) sumq[i-1][j1];q[i][j]sum%2;if(a[i][j]1q[i][j]0) return INF;}///0 0 和1 1 和01都满足状态}int ans0;for(int i0;in;i)///统计转变的次数{for(int j0;jn;j)if(a[i][j]!q[i][j]) ans;}return ans;
}
int main()
{int T;scanf(%d,T);while(T--)///这道题的整体思想 是改变最上面一层的数 然后根据规律向下递推{scanf(%d,n);for(int i0;in;i){for(int j0;jn;j)scanf(%d,a[i][j]);}int ansINF;for(int i0;i(1n);i)///利用状态压缩 将最上面的每种情况 都考虑到ansmin(ans,Q(i));if(ansINF) ans-1;///如果不能转换则输出-1printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/a719525932/p/7158857.html
