- 后院羊问题
-
240901gj花子轩 (EL230810) LV 8 @ 2024-04-21 20:55:47
#include <bits/stdc++.h>
using namespace std;
int sh,wo;
char a[255][255];
bool flag;
void dfs(int x,int y)
{
if(!a[x][y])
{
flag=1;
return ;
}
else if(a[x][y]=='#')
{
return ;
}
else if(a[x][y]=='k')
{
sh++;
}
else if(a[x][y]=='v')
{
wo++;
}
a[x][y]='#';
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main()
{
int n,m,shsum=0,wosum=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!='#')
{
flag=0;
sh=0;
wo=0;
dfs(i,j);
if(!flag)
{
if(sh>wo)
{
shsum+=sh;
}
else
{
wosum+=wo;
}
}
}
}
}
cout<<shsum<<" "<<wosum;
return 0;
}
2 条评论
-
2230134娄耀 (2212238) LV 8 @ 2024-04-27 13:52:51
//可读性要强，用enum #include<bits/stdc++.h> using namespace std; enum Map { Wall,Weslie,Wolffy,Empty }a[255][255]; int n,m,answ,anso,w,o,dir[4][2]={1,0,0,1,-1,0,0,-1}; bool vis[255][255]; void dfs(int x,int y) { for(int i=0;i<4;i++) { int nx=x+dir[i][0]; int ny=y+dir[i][1]; if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||!a[nx][ny]) continue; vis[nx][ny]=true; if(a[nx][ny]==Weslie) w++; else if(a[nx][ny]==Wolffy) o++; dfs(nx,ny); } } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { char ch;cin>>ch; if(ch=='#')a[i][j]=Wall; else if(ch=='.')a[i][j]=Empty; else if(ch=='k')a[i][j]=Weslie; else if(ch=='v')a[i][j]=Wolffy; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]&&!vis[i][j]) { w=o=0; if(a[i][j]==Weslie) w++; else if(a[i][j]==Wolffy) o++; vis[i][j]=true; dfs(i,j); if(w>o) answ+=w; else anso+=o; } cout<<answ<<' '<<anso<<endl; return 0; }-
@ 2024-04-27 14:34:44
学会了AVA
-
-
@ 2024-04-23 19:20:58
是的，但一般来说，bfs时间更优
-
@ 2024-04-23 20:00:16
flood fill算法两种都一样，都是O(n*m)
-
@ 2024-04-23 20:36:48
所以我没说都是bfs更优，而且得在两者通用的情况下
-
- 1
信息
- ID
- 2643
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 30
- 已通过
- 7
- 通过率
- 23%
- 上传者
-
金老师 (zfkin)
