Codeforces Round 928 F. Vlad and Avoiding X

本文主要是介绍Codeforces Round 928 F. Vlad and Avoiding X，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：Problem - F - Codeforces

题目大意：多组询问，给一个7×7的棋盘，上面有W和B二种棋子，棋盘不允许B棋子的左上角，左下角，右上角，右下角也是B，可以让W变成B，也可以让B变成W，问最少的变化次数。

思路：棋盘的纵向为i，横向为j，当(i+j)%2==0,当前点涂为白色，当(i+j)%2==1,当前的点涂为黑色。可以将白色棋盘和黑色棋盘分开观察。对应白色棋盘来说，观察可以知道，如果白色棋盘出现了非法的结构，那么最多变化4次就可以让白色棋盘满足条件，黑色棋盘也是如此。那么就可以设置二个最小值，一个记录白色棋盘，一个记录黑色棋盘。使用dfs分别遍历白色棋盘和黑色棋盘，然后最小值相加就是答案。

特别的：如果遍历白色棋盘，出现非法结构，那么非法结构的棋子一定都在白色棋盘上，黑色棋盘也是。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n' 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,char> pii;
const int N=1e6+10,mod=1e9+7;
char mp[10][10];
ll min1=1e18,min2=1e18;
void dfs1(ll x,ll y,ll sum)
{if(sum>min1||sum>5)return;//超过4次改变一定不是最优的改变 if((x+y)%2==1)//只遍历黑色棋盘 {dfs1(x,y+1,sum);return;}if(y>=7){dfs1(x+1,0,sum);return;}if(x>=7){min1=min(min1,sum);return;}if(mp[x][y]=='B'&&mp[x][y+2]=='B'&&mp[x+1][y+1]=='B'&&mp[x+2][y+2]=='B'&&mp[x+2][y]=='B')//一个非法结构共五个B,分别变化他们，求最小值 {mp[x][y]='W';dfs1(x,y+1,sum+1);mp[x][y]='B';mp[x][y+2]='W';dfs1(x,y+1,sum+1);mp[x][y+2]='B';mp[x+1][y+1]='W';dfs1(x,y+1,sum+1);mp[x+1][y+1]='B';mp[x+2][y+2]='W';dfs1(x,y+1,sum+1);mp[x+2][y+2]='B';mp[x+2][y]='W';dfs1(x,y+1,sum+1);mp[x+2][y]='B';}else dfs1(x,y+1,sum);
}
void dfs2(ll x,ll y,ll sum)
{if(sum>min2||sum>5)return;if((x+y)%2==0){dfs2(x,y+1,sum);return;}if(y>=7){dfs2(x+1,0,sum);return;}if(x>=7){min2=min(min2,sum);return;}if(mp[x][y]=='B'&&mp[x][y+2]=='B'&&mp[x+1][y+1]=='B'&&mp[x+2][y+2]=='B'&&mp[x+2][y]=='B'){mp[x][y]='W';dfs2(x,y+1,sum+1);mp[x][y]='B';mp[x][y+2]='W';dfs2(x,y+1,sum+1);mp[x][y+2]='B';mp[x+1][y+1]='W';dfs2(x,y+1,sum+1);mp[x+1][y+1]='B';mp[x+2][y+2]='W';dfs2(x,y+1,sum+1);mp[x+2][y+2]='B';mp[x+2][y]='W';dfs2(x,y+1,sum+1);mp[x+2][y]='B';}else dfs2(x,y+1,sum);
}
int main()
{ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){for(int i=0;i<7;i++){for(int j=0;j<7;j++)cin>>mp[i][j];}min1=min2=1e18;dfs1(0,0,0);dfs2(0,1,0);cout<<min1+min2<<endl;}return 0;
}

这篇关于Codeforces Round 928 F. Vlad and Avoiding X的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---