牛客小白月赛89-----＞太阳之华

本文主要是介绍牛客小白月赛89-----＞太阳之华，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题有没有和我一样，四联通块理解错了的，我理解成了一个联通块至少有四个方格才能叫四连通块（现在想起来我是XXX）。

一，思路：像这题我可以举一个例子你大概就懂了，如下图：

这种已经是一种极端情况了，红色吃完之后 ，蓝色就只剩下中间那一个了，但是轮到蓝色使他又会像四个方向扩展，导致红色始终都无法将最中间的吃掉，然而蓝色也是无法获胜的，最终平局。所以要么一招制敌，要么就只能平局。还有特殊情况就是红色天崩开局，图上一个棋子也没有那么，红色必输。可以用dfs来遍历所有联通块，看拿一个可以一招制敌，就选他。

二，代码：

#include <iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;const int N=2010;typedef pair<int,int> pii;int n,m;
char arr[N][N];
bool st[N][N];
set<pii> s;//模拟四个方向上的移动
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};//dfs找联通块模板（只是加入计算能被染色的蓝方块个数记录）
void dfs(int x,int y){st[x][y]=true;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a<=n&&a>=1&&b<=m&&b>=1&&!st[a][b]){//用set是为了去重防止重复计数if(arr[a][b]=='.') s.insert({a,b});else dfs(a,b);}}}void Solved() {memset(st,false,sizeof st);cin>>n>>m;//输入加统计初始蓝色方块数量int blue=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>arr[i][j];if(arr[i][j]=='.') blue++;}}//红色天崩开局if(blue==n*m){cout<<"Blue"<<endl;return;}//找联通块模板bool flag=false;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(arr[i][j]=='#'&&!st[i][j]){//因为我们要遍历多个联通块，看有没有可以一招制敌的联通块区域，
//所以set要清空，不能影响后面判断s.clear();dfs(i,j);//一招制敌if(s.size()==blue){flag=true;break;}}}}if(!flag) cout<<"Draw"<<endl;else cout<<"Red"<<endl;}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin>>t;while(t--) {Solved();}return 0;
}

这篇关于牛客小白月赛89-----＞太阳之华的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---