大佬们都睡觉了,55
by yitian_ @ 2024-04-12 23:45:52
@[yitian_](/user/1263486) 应该可以改成bfs
by a_little_carrot @ 2024-04-13 05:47:27
@[yitian_](/user/1263486) 用并查集维护，在放入一个棋子之后合并四个方向相同颜色的棋子的并查集，答案为不同的并查集个数。
by Exp10re @ 2024-04-13 08:38:27
@[yitian_](/user/1263486)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=3000;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
char mp[N][N];
int ans=0;
int a[N][N];
bool v[N][N];
struct node
{
int x,y;
};
void bfs1(int sx,int sy)
{
node now;now.x=sx;now.y=sy;
queue<node>q;
q.push(now);v[sx][sy]=1;
while(!q.empty())
{
node d=q.front();q.pop();
for(int i=0;i<4;i++)
{
node next;next.x=d.x+1;next.y=d.y+1;
if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=n&&!v[next.x][next.y]&&a[next.x][next.y]==1)
{
q.push(next);v[next.x][next.y]=1;
}
}
}
}
void bfs2(int sx,int sy)
{
node now;now.x=sx;now.y=sy;
queue<node>q;
q.push(now);v[sx][sy]=1;
while(!q.empty())
{
node d=q.front();q.pop();
for(int i=0;i<4;i++)
{
node next;next.x=d.x+1;next.y=d.y+1;
if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=n&&!v[next.x][next.y]&&a[next.x][next.y]==2)
{
q.push(next);v[next.x][next.y]=1;
}
}
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='*')
{
a[i][j]=1;//黑棋子
}
if(mp[i][j]=='@')
{
a[i][j]=2;//白棋子
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==1)
{
bfs1(i,j);
ans++;
}
else if(a[i][j]==2)
{
bfs2(i,j);
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
```
这道题用bfs会更好一些 dfs可能会因为递归层数太多而超时
by czy20080428 @ 2024-04-13 08:52:05
@[a_little_carrot](/user/1042960) @[czy20080428](/user/1217367)
谢谢，但是昨天刚学bfs，还没弄懂、、
by yitian_ @ 2024-04-13 16:44:52
@[Exp10re](/user/403069) 谢谢，就是......并查集维护是啥qwq
by yitian_ @ 2024-04-13 16:45:24
@[a_little_carrot](/user/1042960) @[Exp10re](/user/403069) @[czy20080428](/user/1217367)
已关
by yitian_ @ 2024-04-13 16:46:35