2. Ovce
题目ID：13015必做题100分
最新提交：
Wrong Answer
9 分
历史最高：
Wrong Answer
9 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
HYF 家的后院养着一群羊，HYF 由于疲劳睡着了，这时一群饿狼钻进了后院开始攻击羊群，后院是由许多个方格构成的长方形区域，每个方格中用字符’.’表示空地，'#’表示栅栏，'o’表示羊，'v’表示狼，羊和狼所在的格子都是空地。如果从一个空地A沿着水平方向或垂直方向经过一系列的空地能够到达空地 B，则称空地A和空地B属于同一个羊圈。对于能够逃离后院的空地我们认为它不属于任何一个羊圈。当一个羊圈中羊的数量大于狼的数量时，它们会用它们的尖角顶死该羊圈中的狼，否则就将被狼吃掉，最后每个羊圈中只会剩下一种动物。
注意："对于能够逃离后院的空地我们认为它不属于任何一个羊圈"这句话可能有歧义，我们可以无视这句话。并且补充了一组样例来说明题意（看样例2）
输入格式
HYF 家后院的行数R和列数C(3 <= R, C <= 250)，接下来的R行每行包含C个字符，每个字符表示一个格子的情况。
输出格式
仅一行，包含两个用一个空格隔开的整数，表示要求的羊的数量和狼的数量。
样例
Input 1
9 12 .###.#####… #.oo#…#v#. #…o#.#.#.#. #…##o#…#. #.#v#o###.#. #…#v#…#. #…v#v####. .####.#vv.o# …####.
Output 1
3 5
Input 2
3 5 .o#vv .o#v. .v#o.
Output 2
2 3
样例解释
样例1解释：羊圈1中有1只狼和3只羊，羊数量大于狼数量，所以狼会被羊杀死，最终留下3只羊。羊圈2中有1只狼和1只羊，狼数量等于羊数量，所以它们会被狼吃掉，最终留下0只羊。羊圈3中有3只狼和1只羊，狼数量大于羊数量，所以羊会被狼吃掉，最终留下0只羊。所以最终留下3只羊和5只狼。
样例2解释：羊圈1中有1只狼和2只羊，羊数量大于狼数量，所以狼会被羊杀死，最终留下2只羊。所以最终留下2只羊和3只狼。
数据范围
30%的数据：R, C <= 30
100%的数据: 3 <= R, C <= 250
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char mp[255][255];
int vis[255][255];
int n,m,o,v;
int hy,hl;
struct node{
int x,y;
};
void bfs(int sx,int sy){
queue<node>que;
que.push({sx,sy});
vis[sx][sy]=1;
int cnto=0,cntv=0;
while(!que.empty()){
node hd=que.front();
que.pop();
if(mp[hd.x][hd.y]=='o')o++;
else if(mp[hd.x][hd.y]=='v')v++;
for(int i=0;i<4;i++){
int nx=hd.x+dx[i];
int ny=hd.y+dy[i];
if(nx>n||ny>n||nx<1||ny<1||vis[nx][ny]!=0)continue;
vis[nx][ny]=1;
que.push({nx,ny});
}
}
if(o>v){
hy+=o;
}
else hl+=v;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==0&&mp[i][j]!='#')
bfs(i,j);
}
}
cout<<hy<<" "<<hl;
return 0;
}