- 后院羊问题
- 2024-04-17 21:01:32 @
//不就是一个种子填充算法吗
#include<bits/stdc++.h>
using namespace std;
int r,c;
char a[250][250];
struct st
{
int xx,yy;
st(int xx1,int yy1){xx=xx1;yy=yy1;}
};
queue<st>q;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>a[i][j];
int ansk=0,ansv=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(a[i][j]!='#')
{
int ck=0,cv=0;
q.push(st(i,j));
if(a[i][j]=='k')ck++;
if(a[i][j]=='v')cv++;
a[i][j]='#';
while(!q.empty())
{
int x=q.front().xx,y=q.front().yy;
for(int k=0;k<4;k++)
{
int nx=x+dir[k][0],ny=y+dir[k][1];
if(a[nx][ny]=='#'||nx<1||nx>r||ny<1||ny>c)continue;
if(a[nx][ny]=='k')ck++;
if(a[nx][ny]=='v')cv++;
a[nx][ny]='#';
q.push(st(nx,ny));
}
q.pop();
}
if(ck>cv)cv=0;
else ck=0;
ansk+=ck;ansv+=cv;
}
}
cout<<ansk<<' '<<ansv;
return 0;
> }
2 条评论
-
240803gj徐嘉昊 (2212224徐嘉昊) LV 10 @ 2024-04-19 20:31:17
兄弟,宽搜不是这么打的
-
2024-04-19 20:29:27@
不就是一个种子填充算法吗
#include<bits/stdc++.h> using namespace std; char mp[255][255]; int r,c,w,s; short dir[4][2]={0,1,1,0,0,-1,-1,0}; struct jl { int x,y; }; jl tool; void bfs(int i,int j) { int wa=0,sa=0; if(mp[i][j]=='k')sa++; if(mp[i][j]=='v')wa++; queue<jl>q; tool.x=i,tool.y=j; q.push(tool); mp[i][j]='#'; while(!q.empty()) { int x=q.front().x,y=q.front().y; for(int k=0;k<4;k++) { int nx=x+dir[k][0],ny=y+dir[k][1]; if(mp[nx][ny]!='#'&&nx>1&&nx<r&&ny>1&&ny<c) { if(mp[nx][ny]=='k')sa++; if(mp[nx][ny]=='v')wa++; mp[nx][ny]='#'; tool.x=nx,tool.y=ny;q.push(tool); } } q.pop(); } if(sa>wa)s+=sa; else w+=wa; } signed main() { ios::sync_with_stdio(false); cin>>r>>c; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) cin>>mp[i][j]; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(mp[i][j]!='#') bfs(i,j); cout<<s<<' '<<w<<endl; return 0; }
23ms,超不了时
- 1
信息
- ID
- 2643
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 30
- 已通过
- 7
- 通过率
- 23%
- 上传者