广岛的尾道市,盘踞着以“孔明”与“造雨人”为首的帮派——“JUSTIS”。
一次偶然的经历,“堂岛之龙”桐生一马从 JUSTIS 组员手上救下了 JUSTIS 的创建者 JOE。
在得知 JUSTIS 在“孔明”与“造雨人”的控制下已成为一个为非作歹的邪恶帮派后,桐
生联手同伴们毅然成立了“桐生会”,与 JUSTIS 展开了包括帮派火拼在内的对抗。
在一次战役里,总战场在地形的限制下被划分成许多子战场。总战场可以看作是由许多方格
组成的长方形区域,每个方格中字符‘.’表示空地,‘#’表示墙体,‘o’表示桐生会
组员,‘v’表示 JUSTIS 组员。桐生会组员和 JUSTIS 组员所在的格子都是空地。
如果从一个空地 A 沿着水平方向或垂直方向经由一系列的空地能够到达空地 B,则称空地
A 和空地 B 联通,或属于同一个子战场。特别地,与总战场外界联通的空地不属于任何子
战场。
当某个子战场中桐生会组员比 JUSTIS 组员多时,其中的桐生会组员将无伤打倒所有
JUSTIS 组员,否则就将全被 JUSTIS 组员无伤打倒。最后每个子战场中只会剩下一个帮派
的成员。
请你对给定的总战场布局,计算战役结束后所有子战场中的桐生会组员总数与 JUSTIS 组员
总数。
Input
第一行包含两个用空格隔开的自然数 R 和 C,R 表示总战场的行数,C 表示列数,接下
来的 R 行每行包含 C 个字符,每个字符表示一个格子的情况。
Output
仅一行,包含两个用一个空格隔开的整数,表示要求的桐生会组员的数量和 JUSTIS 组员
的数量。
Sample.in
9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.
Sample.out
3 5
数据范围:
30%的数据, R, C <= 30
100%的数据,3 <= R, C <= 250
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[35][35];
int vis[35][35];
struct node{
int x,y;
}z;
int onezs=0;
int tuzs=0;
int ys[5][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs(int x,int y){
queue <node> q;
z.x=x;
z.y=y;
q.push(z);
int tu=0,one=0;
while(!(q.empty())){
node dlt=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=dlt.x+ys[i][0];
int ny=dlt.y+ys[i][1];
if(nx<1 || nx>m || ny<1 || ny>n) continue;
if(vis[nx][ny]!=0 || a[nx][ny]=='#') continue;
vis[nx][ny]=1;
if(a[nx][ny]=='o') one++;
else if(a[nx][ny]=='v') tu++;
}
}
if(one<tu) tuzs+=tu;
else onezs+=one;
}
int main(){
// freopen("ovce.in","r",stdin);
// freopen("ovce.out","w",stdout);
memset(vis,0,sizeof(vis));
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<=n;j++){
if(a[i][j]=='#') continue;
else bfs(i,j);
}
cout<<onezs<<" "<<tuzs;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[35][35];
int vis[35][35];
struct node{
int x,y;
}z;
int onezs=0;
int tuzs=0;
int ys[5][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs(int x,int y){
queue q;
z.x=x;
z.y=y;
q.push(z);
int tu=0,one=0;
while(!(q.empty())){
node dlt=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=dlt.x+ys[i][0];
int ny=dlt.y+ys[i][1];
if(nx<1 || nx>m || ny<1 || ny>n) continue;
if(vis[nx][ny]!=0 || a[nx][ny]=='#') continue;
vis[nx][ny]=1;
if(a[nx][ny]=='o') one++;
else if(a[nx][ny]=='v') tu++;
}
}
if(one<tu) tuzs+=tu;
else onezs+=one;
}
int main(){
// freopen("ovce.in","r",stdin);
// freopen("ovce.out","w",stdout);
memset(vis,0,sizeof(vis));
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<=n;j++){
if(a[i][j]=='#') continue;
else bfs(i,j);
}
cout<<onezs<<" "<<tuzs;
return 0;
}