bdpq偶数边长基本思路

本次给大家带来的是bdpq中偶数边长的基本思路，希望这份攻略能给大家一份思路，帮助大家更好的解决在这个游戏中碰到的问题~本篇仅讲解偶数边长的思路，暂无奇数内容。

首先，如果矩阵边长是偶数，那么我们能得到一个简单的结论：

假设我想让第二行、第三列的一个 ‘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][i] == 'b'){mmp[x][i] = 'p';}

else if(mmp[x][i] == 'd'){mmp[x][i] = 'q';}

if(mmp[i][y] == 'b'){mmp[i][y] = 'p';}

else if(mmp[i][y] == 'd'){mmp[i][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[i] + 1); }

queue <pair<int,int> > Q;

for(int i = 1;i <= N;i ++){ for(int j = 1;j <= N;j ++){ if(mmp[i][j] == 'b' || mmp[i][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[i][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][i][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][i] = 1 - ans[k][x][i]; ans[k][i][y] = 1 - ans[k][i][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[i] + 1); }

for(int i = 1;i <= N;i ++){ for(int j = 1;j <= N;j ++){ if(mmp[i][j] == 'b' || mmp[i][j] == 'd'){ solve(1,i,j); if(mmp[i][j] == 'b'){mmp[i][j] = 'p';}

else if(mmp[i][j] == 'd'){mmp[i][j] = 'q';} } } }

for(int i = 1;i <= N;i ++){ for(int j = 1;j <= N;j ++){ if(mmp[i][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][i][j] << " "; }cout << endl; } } } return 0; } [/x]