网站后台怎么做水印图片,新手学做网站 pdf,大连淘宝网站建设,彩票网站怎么样建设文章目录1. 题目1.1 题目链接1.2 题目大意1.3 解题思路2. 代码2.1 Wrong Answer代码2.2 Accepted代码1. 题目
1.1 题目链接
http://poj.org/problem?id1753
1.2 题目大意
一个黑白棋子的棋盘#xff0c;一个反过来周围四个也跟着反过来(如果存在的话)#xff0c;颜色取反…
文章目录1. 题目1.1 题目链接1.2 题目大意1.3 解题思路2. 代码2.1 Wrong Answer代码2.2 Accepted代码1. 题目
1.1 题目链接
http://poj.org/problem?id1753
1.2 题目大意
一个黑白棋子的棋盘一个反过来周围四个也跟着反过来(如果存在的话)颜色取反问最少反转次数使得颜色全白或者全黑不存在解的话输出信息。
1.3 解题思路
采用回溯算法暴力枚举
2. 代码
2.1 Wrong Answer代码
/*** description: * author: michael ming* date: 2019/7/11 22:09* modified by: */
#include iostream
#include string
using namespace std;
bool a[4][4];
bool isok()//判断是否都是同种颜色
{int i, j;for(i 0; i 4; i){for(j 0; j 4; j){if(a[i][j] ! a[0][0]){return false;}}}return true;
}
void flipAndUpdate(int r, int c)//翻转rc处及其周围棋子
{a[r][c] !a[r][c];if(r-1 0)a[r-1][c] !a[r-1][c];if(r1 4)a[r1][c] !a[r1][c];if(c-1 0)a[r][c-1] !a[r][c-1];if(c1 4)a[r][c1] !a[r][c1];
}
void flip(int r, int c,int curstep, long minstep)
{if(isok()){if(curstep minstep)minstep curstep;return;}if(c1 4)flip(r,c1,curstep,minstep);else if(c1 4 r1 4)flip(r1,0,curstep,minstep);flipAndUpdate(r,c);curstep;if(c1 4)flip(r,c1,curstep,minstep);else if(c1 4 r1 4)flip(r1,0,curstep,minstep);flipAndUpdate(r,c);//翻完了还要复原
}
int main()
{string s;int i, j;long minstep 65536;for(i 0; i 4; i){cin s;for(j 0; j 4; j){if(s[j] b)a[i][j] 1;elsea[i][j] 0;}}flip(0,0,0,minstep);if(minstep 65536)cout Impossible endl;elsecout minstep;return 0;
}2.2 Accepted代码 上面代码范围有问题改动如下 AC 代码如下
/*** description: * author: michael ming* date: 2019/7/11 22:09* modified by: */
#include iostream
#include string
using namespace std;
bool a[5][5];
bool isok()//判断是否都是同种颜色
{int i, j;for(i 0; i 4; i){for(j 0; j 4; j){if(a[i][j] ! a[0][0]){return false;}}}return true;
}
void flipAndUpdate(int r, int c)//翻转rc处及其周围棋子
{a[r][c] !a[r][c];if(r-1 0)a[r-1][c] !a[r-1][c];if(r1 4)a[r1][c] !a[r1][c];if(c-1 0)a[r][c-1] !a[r][c-1];if(c1 4)a[r][c1] !a[r][c1];
}void flip(int r, int c,int curstep, long minstep)
{if(isok()){if(curstep minstep)minstep curstep;return;}if(r 4)return;if(c1 4)flip(r,c1,curstep,minstep);else if(c1 4)flip(r1,0,curstep,minstep);flipAndUpdate(r,c);curstep;if(c1 4)flip(r,c1,curstep,minstep);else if(c1 4)flip(r1,0,curstep,minstep);flipAndUpdate(r,c);//翻完了还要复原
}
int main()
{string s;int i, j;long minstep 65536;for(i 0; i 4; i){cin s;for(j 0; j 4; j){if(s[j] b)a[i][j] 1;elsea[i][j] 0;}}flip(0,0,0,minstep);if(minstep 65536)cout Impossible endl;elsecout minstep;return 0;
}
