poj 1753题学习笔记
1753 题是一个基本的枚举算法的题，基本解题思路就是暴力枚举，但是我们需要知道即便是暴力枚举，也是需要认真分析问题的。
题意：有一个4*4的棋盘,棋盘上有黑白格,每一次你可以翻其中的一个格子。一个格子(x,y)如果被翻,它相邻的前后左右四个格子（如果在棋盘上）也要翻转。现在给你一个初始的棋盘状态，问把这个棋盘翻转到全黑或全白的最少次数；若不能达到全黑或全白，输出Impossible。
思路：只有4*4的棋盘，同时格子只有黑白两面。对于同一个格子，翻两次和不翻没有区别。同时，我们会发现，假如第一行的状态已经确定，那么剩下的行的翻法其实也是确定了的。这样我们从原来需要枚举65536种，到现在只需要枚举第一行16种即可，所以，我们只需要按照求4个数的子集的方式，枚举第一行的翻法即可枚举所有可能形式。
所以，我们需要一个子集递归方法，一个步数求解方法，还有小方法例如判断当前是否全黑或全白、将当前棋子性质翻转等，即可实现枚举。
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
//成功
//暴力枚举，通过枚举第一行元素的组合方式进行暴力搜索
string s[4];//输入矩阵
string tmp[4];//当前棋子状态矩阵
bool b[4];//判断枚举，1-4的子集生成
int foot=100;//步子数
void back2(int x,int y){//将tmp中的元素性质翻转，例如b转成w，w转成b
if(tmp[x][y]=='b')tmp[x][y]='w';
else
tmp[x][y]='b';
}
bool test(){//判断输入矩阵是否直接为全黑或者全白
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(s[i][j]!=s[0][0])return false;
}
}
return true;
}
bool test2(){//判断当前棋子矩阵是否直接为全黑或者全白
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(tmp[i][j]!=tmp[0][0])return false;
}
}
return true;
}
void genera(char flag){//将当前棋子矩阵变为全黑或者全白的步数
int root=0;
for(int i=0;i<4;i++){//将当前状态初始化为输入状态
for(int j=0;j<4;j++){
tmp[i][j]=s[i][j];
}
}
for(int i=0;i<4;i++){//根据第一行的子集进行转换，即改变第一行的状态
if(b[i]){
root++;
back2(0,i);
back2(1,i);
if(i<=2)back2(0,i+1);
if(i>=1)back2(0,i-1);
}
}
for(int i=0;i<4;i++){//根据第一行改变第二行
if(tmp[0][i]!=flag){
root++;
tmp[0][i]=flag;
back2(1,i);
if(i<=2)back2(1,i+1);
if(i>=1)back2(1,i-1);
back2(2,i);
}
}
for(int j=2;j<4;j++){//改变第三和第四行
for(int i=0;i<4;i++){
if(tmp[j-1][i]!=flag){
root++;
tmp[j-1][i]=flag;
back2(j,i);
if(i<=2)back2(j,i+1);
if(i>=1)back2(j,i-1);
if(j<=2)back2(j+1,i);
}
}
}
if(test2()&&root<foot){//如果当前棋子为全黑或全白则改变最小步数
foot=root;
}
}
void gen(int y){//第一行的全部子集
if(y==4){
genera('b');//全黑
genera('w');//全白
}
else{
b[y]=true;//使用位向量法构造第一行的全部子集数
gen(y+1);
b[y]=false;
gen(y+1);
}
}
int main(){
for(int i=0;i<4;i++){
cin>>s[i];
b[i]=false;
}
if(test())
cout<<0<<endl;//判断当前是否为已经排列好的矩阵
else
{//构造矩阵
gen(0);
if(foot!=100){
cout<<foot<<endl;
}
else
cout<<"Impossible"<<endl;//如果无法生成则输出
}
return 0;
}文章浏览阅读231次。要修改针对首页中的POST请求的测试。希望视图把新添加的待办事项存入数据库，而不是直接传给响应。为了测试这个操作，要在现有的测试方法test_can_save_a_post_request中添加3行新代码# lists/tests.pydeftest_can_save_a_post_request(self):response= self.client.post(‘/‘, data={‘item_..._django http post mysql
文章浏览阅读295次，点赞4次，收藏4次。其中一项重要的技术是s32k144 uds bootloader软件，它结合了上位机周立功ZCANPRO脚本，操作简单且非常适合学习调试。对于汽车电子开发人员来说，s32k144 uds bootloader软件为他们提供了一个快速而可靠的开发平台，使他们能够更好地进行软件的开发和调试工作。总结来说，s32k144 uds bootloader软件结合了上位机周立功ZCANPRO脚本，为汽车制造商和汽车电子开发人员带来了许多便利和优势。它提供了一个高效和安全的方式，实现对ECU固件的更新和调试。_zcanpro脚本无法运行
文章浏览阅读526次。今天无意看到别人的博客背景特别炫酷,黑客呀,书法呀,纯色等,自己也摸索着找了下在哪更换,现在告诉大家。vip级别越高能用的皮肤的背景皮肤越多,选中下面的个性皮肤，我目前只有三级，所以能用的皮肤不多。我们需要多写文章或者做任务等方式提高自己的等级,等级越高可用的皮肤越多。1首先进入CSDN点击自己头像旁边的创作中心。CSDN设置主题背景。_csdn设置背景
文章浏览阅读379次。1. Java环境开发搭建1.1 Java编程语言1. 什么是Java编程语言编程语言就是人类和计算机沟通的桥梁编程语言的发展史 机器语言: 机器语言是用二进制就是最开始01代码组成的计算机能够直接识别和执行的一种机器指令的集合 汇编语言 汇编语言是由一些指令或者符号组合而成 高级语言 高级语言是以人类的日常语言为基础的一种编程语言,是用来人类更加易于接受的文字来表示(英文) C++,C#,php,python,Java(Java是全世界最好的语_jre jdk的安装及程序设计原理
文章浏览阅读187次。你是不是发现你的JDK 明明用的 17，结果编译使用的是 1.5 或者 1.8。在你的 pom.xml 里添加 maven 编译插件，版本 17。对没错，就是这个 java compiler 在捣鬼。_idea中,java compile,use compiler老是重置
文章浏览阅读4.7k次，点赞6次，收藏8次。你是否遇到过这种情况，异地办公或者不在公司，想找到一篇课件或者想找到某个文件，你只记得资料文件或者课件里的某一句话，却不记得它的名字，你花了大量的时间，大量的精力，却怎么也找不到这个文件在哪个地方，看完本篇文章，希望能解决你的这个问题！Any TXT结合[cpolar](cpolar - 安全的内网穿透工具)内网穿透帮你实现异地办公寻迅速查找到公司电脑的文件！之前曾给大家介绍过搜索工具Everything，搜索速度很快，但是不足的是这个只能根据文件名进行搜索。_anytxt
文章浏览阅读139次。本课题研究的高校实验室资产管理系统，主要功能模块包括后台首页，轮播图，公告管理，资源管理，系统用户（管理员，普通用户，普管用户），模块管理（资产信息，资产分类，设备借用，设备归还，耗材信息，耗材领用，库存信息，入库记录，出库记录，资产使用报告，设备图，耗材图，维护信息）等，采取面对对象的开发模式进行软件的开发和硬体的架设，能很好的满足实际使用的需求，完善了对应的软体架设以及程序编码的工作，采取MySQL作为后台数据的主要存储单元，采用SpringBoot框架进行系统的开发，实现了本系统的全部功能。_实验室资产管理系统的设计与实现
文章浏览阅读54次。所谓带权并查集本题所求的不止是两个编号之间是否有关系，还要求两个编号之间有什么关系，这就要求我们维护多个数组，fa[]数组维护两个编号之间的连通性，dis[]维护编号为i的战舰到fa[i]之间的距离，num[]维护编号为i的战舰所在的那一列有多少战舰。find函数int find(int x){ if(x!=fa[x]){ int k=fa[x]; ..._洛谷p1196
文章浏览阅读2.8k次，点赞2次，收藏7次。表格内部分隔线设置表格内部分割线是rules参数，它有三个值(cols,rows,none)。当rules=cols时，隐藏表格内部的横向分隔线，显示纵向的分割线；当rules=rows时，隐藏表格内部的纵向分隔线，显示横向的分割线；当rules=none时，将表格内部纵向分隔线和横向分隔线全部隐藏，只显示表格的外框。(rules=groups好像这个属性和none是一样..._table分割线
文章浏览阅读924次。对象的树结构一个树结构由两种节点组成：树枝节点和树叶节点。树枝节点可以有子节点，而一个树叶节点不可以有子节点。除了根节点外，其它节点有且只有一个父节点。注意：一个树枝节点可以不带任何叶子，但是它因为有带叶子的能力，因此仍然是树枝节点，而不会成为叶节点。一个树叶节点永远不可能带有子节点。二、 合成模式概述下图所示的类图省略了各个角色的细节。 可以看出，上面的类图结构涉及到三个_合成模式 csdn 男装
文章浏览阅读774次。原标题：Java开发工程师职业发展及晋升路线图对于一个Java开发工程师来讲，了解Java开发的职业发展及晋升路线是十分有必要的。不仅可以帮助自己更好地规划对未来的职业发展，而且在求职时有了更加明确的方向。那么Java开发工程师的职业发展及晋升路线图是怎么样的呢？我们一起来看看。 1.Java程序员这是Java开发工程师的第一阶段了，一般是刚入门Java行业者。这一阶段主要是掌握了一定的Java编..._java开发工程师路线图
文章浏览阅读1w次。<input type="text" maxlength="11" placeholder="请输入联系人电话" v-model="form.phone" />//这样的输入框，绑定的是data中的form对象上的phone字段。在mounted钩子函数里边写：this.form.phone = '1888888888';//这样在页面上时候不会随着输入框值改变..._表单内输入框无法输入双向绑定失效