oiclass P1315. 羊和狼

· · 个人记录

问题描述

米基家的后院养着一群羊，米基由于疲劳睡着了，这时一群饿狼钻进了后院开始攻击羊群，后院是由许多个方格构成的长方形区域，每个方格中用字符 . 表示空地，# 表示栅栏，o 表示羊，v 表示狼，羊和狼所在的格子都是空地。

如果从一个空地 A 沿着水平方向或垂直方向经过一系列的空地能够到达空地 B，则称空地 A 和空地 B 属于同一个羊圈。对于能够逃离后院的空地我们认为它不属于任何一个羊圈。

当一个羊圈中羊的数量大于狼的数量时，它们会用它们的尖角顶死该羊圈中的狼，否则就将被狼吃掉，最后每个羊圈中只会剩下一种动物。

写一个程序统计战斗结束后所有羊圈中羊的总数和狼的总数。

输入格式

输入文件的第一行包含两个用空格隔开的自然数 R 和 C，其中 3≤R,C≤250， R 表示米基家后院的行数， C 表示列数，接下来的 R 行每行包含 C 个字符，每个字符表示一个格子的情况。 输出格式

输出文件仅一包含两个用一个空格隔开的整数，表示要求的羊的数量和狼的数量。

输入数据 1

9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.

输出数据 1

3 5

其实这题矩阵存储图，或者可以用BFS 或 DFS 。题意为将每一个点与上下左右的邻接点（非‘#“标记）形成路径进行构图。利用深搜或广搜的思路求封闭于区域内的狼数和羊数，对两者的数据进行处理。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int r,c,sleepnomber,wolfnomber,a[300][300],sleep,wolf,xx[5]={-1,0,1,0},yy[5]={0,1,0,-1};
char b;
bool flag;
void bfs(int x,int y){
    if((x<1||x>r||y<1||y>c)) {
        flag=false;
        return ;
    }
    else if(a[x][y]==0) return ;
    else if(a[x][y]==1) sleep+=1;
    else if(a[x][y]==2) wolf+=1;
    a[x][y]=0;
    for(int i=0;i<4;i++) bfs(x+xx[i],y+yy[i]);
}
int main() {
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>b;
            if(b=='o')a[i][j]=1;
            else if(b=='v') a[i][j]=2;
            else if(b=='#') a[i][j]=0;
            else a[i][j]=3;
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(a[i][j]>0){
                sleep=0,wolf=0;
                flag=true;
                bfs(i,j);
                //cout<<sleep<<" "<<wolf<<endl;
                if(flag==true){
                    if(sleep<=wolf) wolfnomber+=wolf;
                    else sleepnomber+=sleep;
                }
            }
        }
    }
    cout<<sleepnomber<<" "<<wolfnomber;
}