poj1222 高斯消元
2024-08-27 02:40:57
给了一个01矩阵然后选在一个点1变0或者0变1 然后 与他相邻的 数也相应的变成相反的数,问最后求出一种方案把他们变成全0 将每一个位置上的状态看做一个变元,30个变元,列出30个异或方程
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std; #define eps 1e-9
const int MAXN=;
int a[MAXN][MAXN],x[MAXN];//方程的左边的矩阵和等式右边的值,求解之后x存的就是结果
int equ,var;//方程数和未知数个数
int Gauss()
{
int i,j,row,col,max_r;
equ=var=;
for(row=,col=;row<equ&&col<var;row++,col++)
{
max_r=row;
for(i=row+;i<equ;i++)
if(a[i][col])
{ max_r=i; break; }
if(row!=max_r)
{ for(j=col;j<var;j++)
swap(a[row][j],a[max_r][j]);
swap(x[row],x[max_r]); }
for(i=;i<equ;i++)
if(i!=row&&a[i][col])
{
x[i]^=x[row];
for(j=col+;j<var;j++)a[i][j]=a[i][j]^a[row][j];
a[i][col]=;
}
}
return ;
}
int dx[]={,,,-};
int dy[]={,-,,};
int idmark[][];
int main()
{
for(int i=; i<; i++)
for(int j=; j<; j++)
idmark[i][j]=i*+j;
int cas;
scanf("%d",&cas);
for(int cc=; cc<=cas ; cc++)
{
for(int i=; i<; i++)
{
scanf("%d",&x[i]);
}
memset(a,,sizeof(a));
for(int i=; i<; i++)
for(int j=; j<; j++){
a[ idmark[i][j] ][ idmark[i][j] ] = ; for(int k=; k<; k++){ int tx= i+dx[k]; int ty= j+dy[k]; if(tx>=&&ty>=&&tx<&&ty<)
a[ idmark[i][j] ][ idmark[tx][ty] ]=; }
}
Gauss();
printf("PUZZLE #%d\n",cc);
int cur=;
for(int i=; i<; i++)
for(int j=; j<; j++)
printf("%d%c",x[cur++],j==?'\n':' ');
} return ;
}
最新文章
- RAP在centos上的部署
- UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode byte 0xff in position 0: illegal multibyte sequence
- Java中对象构造
- 作为一个web开发人员,哪些技术细节是在发布站点前你需要考虑到的
- 数据结构-Hash表
- sonar之安装篇
- vim自动补全:go
- EXE文件结构和读取方法
- TOGAF架构开发方法(ADM)之迁移规划阶段
- 两句话概括cmd和amd的区别
- FFmpeg源代码结构图 - 编码
- java设计模式(2)---六大原则
- angular 1.2.29版本下 动态添加多个表单、 校验全部、 提交 、ng-form方案
- BZOJ3070 : [Pa2011]Prime prime power 质数的质数次方
- 【ShareCode】不错的技术文章 -- 如何使用异或(XOR)运算找到数组中缺失的数?
- 【转】如何将MySQL数据目录更改为CentOS 7上的新位置
- .Net Reactor 单个dll或exe文件的保护
- java高级精讲之高并发抢红包~揭开Redis分布式集群与Lua神秘面纱
- 一道另类的区间dp题 -- P3147 [USACO16OPEN]262144
- Linux - awk 文本处理工具二
热门文章
- 20165336 2017-2018-2《Java程序设计》第6周学习总结
- SpringBoot 使用RedisTemplate操作Redis
- 跨域的问题(nginx解决才是王道)
- 使用DigitalOcean控制台访问Droplet(远程服务器)
- TCP/IP协议栈基础知识
- git branch 命令查看分支、删除远程分支、本地分支
- [硬件]Urg_viewer数据读取
- 【Java】-NO.16.EBook.4.Java.1.010-【疯狂Java讲义第3版 李刚】- 异常
- jenkins 多用户同时触发构建—简单实用
- [LeetCode] 414. Third Maximum Number_Easy