题目描述
【题目描述】
HYF 家的后院养着一群羊，HYF 由于疲劳睡着了，这时一群饿狼钻进了后院开始攻击羊群，后院是由许多个方格构成的长方形区域，每个方格中用字符’.’表示空地，'#’表示栅栏，'o’表示羊，'v’表示狼，羊和狼所在的格子都是空地。
如果从一个空地A沿着水平方向或垂直方向经过一系列的空地能够到达空地 B，则称空地A和空地B属于同一个羊圈。对于能够逃离后院的空地我们认为它不属于任何一个羊圈。
当一个羊圈中羊的数量大于狼的数量时，它们会用它们的尖角顶死该羊圈中的狼，否则就将被狼吃掉，最后每个羊圈中只会剩下一种动物。
【输入文件】
第一行包含两个用空格隔开的自然数 R 和 C，R 表示 HYF 家后院的行数，C表示列数，接下来的R行每行包含C个字符，每个字符表示一个格子的情况。
【输出文件】
仅一行，包含两个用一个空格隔开的整数，表示剩余的羊的数量和狼的数量。
【数据规模】
30%的数据：R,C<=30R,C<=30
100%的数据: 3<=R,C<=2503<=R,C<=250
注意："对于能够逃离后院的空地我们认为它不属于任何一个羊圈"这句话可能有歧义，我们可以无视这句话。并且补充了一组样例来说明题意（看样例2）
样例1输入：
9 12 .###.#####… #.oo#…#v#. #…o#.#.#.#. #…##o#…#. #.#v#o###.#. #…#v#…#. #…v#v####. .####.#vv.o# …####.
样例1输出：
3 5
样例2输入：
3 5 .o#vv .o#v. .v#o.
样例2输出：
2 3
代码
#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
int v[1005][1005];
int n,m;
int ys,ls;
int hys,hls;
int dy[5]={0,0,1,-1};
int dx[5]={1,-1,0,0};
struct Node{
int x;
int y;
};
void bfs(int X,int Y){
queue<Node> qu;
qu.push({X,Y});
v[X][Y]=1;
while(!qu.empty()){
Node now=qu.front();
qu.pop();
if(a[now.x][now.y]=='o'){
ys++;
}
if(a[now.x][now.y]=='v'){
ls++;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i];
int ny=now.y+dy[i];
if(nx<0||ny<0||nx>=n||ny>=m||v[nx][ny]==1||a[nx][ny]!='#'){
continue;
}
qu.push({nx,ny});
v[nx][ny]=1;
}
}
if(ls>=ys){
hls+=ls;
}else{
hys+=ys;
}
ls=0;
ys=0;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(v[i][j]==0&&a[i][j]!='#'){
bfs(i,j);
}
}
}
cout<<hys<<" "<<hls;
return 0;
}