对于此类问题的按奇偶性分类讨论的暴力解法。

﹏泪染倾城°

177 阅读

发布于 2020-06-25

这个小游戏成功吸引了一个即将退役ACMer的我的兴趣，因为这个题和我做过的一道题太像了。

那么首先，我要声明，这个解法是一个无脑的暴力解法，不一定是步数最少的最优解，但一定是一个可行解，因为最优解应该需要用高斯消元求解方程组，本帖讨论的是按奇偶性分类的解法。

首先，如果矩阵边长是偶数，那么我们能得到一个简单的结论：
假设我想让第二行、第三列的一个 ‘p’ 变成 ‘q’ ，那么只需要对于第二行和第三列的所有格子都往右翻一下，但其中第二行、第三列的那个格子只能翻一下（具体如下图，以 4 * 4 为例，蓝色代表目标格子，所有染色的格子都翻一次），那么我们发现，除了第二行、第三列的目标格子变成 ‘q’ ，剩下的所有格子都没有变化。

这是因为，所有别的格子的改变次数都是偶数次，除了蓝色格子是奇数次（n+n-1）。那么，如果我们想把所有格子变成 ‘p’，只需要先把所有‘d’和‘b’，都用上述方法变成‘q’和‘p’，再把所有‘q’都变成‘p’就完成任务了。

那么如果矩阵边长是奇数又如何？
首先，我们知道，所给的矩阵一定是有可行解的。
那么，如果矩阵边长是奇数，对于任意的一个矩阵，假设我们想把所有格子变成 ‘p’，只需要先把所有的'd'和’b‘标记起来，再把所有的标记都向上或向下翻一下，此时我们一定能得到一个只含有 ‘p’ 和 ‘q’ 的矩阵，对于这个矩阵，再次标记所有的‘q’，标记过后再次把所有的标记点都向左或者向右翻一次，那么一定能够得到一个全是‘p’的矩阵。

C++代码粘在下面了，留给各位参考

运行图：
奇数矩阵：

偶数矩阵：

///奇数解
#include<bits/stdc++.h>
using namespace std;
int ans[5][5][5];
char mmp[10][10];
int N;
void Flip(int x,int y){
for(int i = 1;i <= N;i ++){
if(mmp[x] == 'b'){mmp[x] = 'p';}
else if(mmp[x] == 'd'){mmp[x] = 'q';}
if(mmp[y] == 'b'){mmp[y] = 'p';}
else if(mmp[y] == 'd'){mmp[y] = 'q';}
}
if(mmp[x][y] == 'b'){mmp[x][y] = 'p';}
else if(mmp[x][y] == 'd'){mmp[x][y] = 'q';}
}

void solve(queue<pair<int,int> > Q,int k){
while(Q.size()){
pair<int,int> t = Q.front();
Q.pop();
ans[k][t.first][t.second] = 1 - ans[k][t.first][t.second];
Flip(t.first,t.second);
}
}

int main(){
while(cin >> N){
memset(ans,0,sizeof ans);
for(int i = 1;i <= N;i ++){
scanf("%s",mmp + 1);
}
queue <pair<int,int> > Q;
for(int i = 1;i <= N;i ++){
for(int j = 1;j <= N;j ++){
if(mmp[j] == 'b' || mmp[j] == 'd'){
Q.push(make_pair(i,j));
}
}
}
solve(Q,1);
while(Q.size()){Q.pop();}
for(int i = 1;i <= N;i ++){
for(int j = 1;j <= N;j ++){
if(mmp[j] == 'q'){
Q.push(make_pair(i,j));
}
}
}
solve(Q,2);
for(int k = 1;k < 3;k ++){
if(k == 1){printf("flip it down or up :\n");}
else{printf("flip it right or left :\n");}
for(int i = 1;i <= N;i ++){
for(int j = 1;j <= N;j ++){
cout << ans[k][j] << " ";
}cout << endl;
}
}
}
return 0;

}

///偶数解
#include<bits/stdc++.h>
using namespace std;
int ans[5][5][5];
char mmp[10][10];
int N;
void solve(int k,int x,int y){
for(int i = 1;i <= N;i ++){
ans[k][x] = 1 - ans[k][x];
ans[k][y] = 1 - ans[k][y];
}
ans[k][x][y] = 1 - ans[k][x][y];
}

int main(){
while(cin >> N){
memset(ans,0,sizeof ans);
for(int i = 1;i <= N;i ++){
scanf("%s",mmp + 1);
}
for(int i = 1;i <= N;i ++){
for(int j = 1;j <= N;j ++){
if(mmp[j] == 'b' || mmp[j] == 'd'){
solve(1,i,j);
if(mmp[j] == 'b'){mmp[j] = 'p';}
else if(mmp[j] == 'd'){mmp[j] = 'q';}
}
}
}
for(int i = 1;i <= N;i ++){
for(int j = 1;j <= N;j ++){
if(mmp[j] == 'q'){
solve(2,i,j);
}
}
}
for(int k = 1;k < 3;k ++){
if(k == 1){printf("flip it down or up :\n");}
else{printf("flip it right or left :\n");}
for(int i = 1;i <= N;i ++){
for(int j = 1;j <= N;j ++){
cout << ans[k][j] << " ";
}cout << endl;
}
}
}
return 0;

}