游记"/>
D. 1.绿纹龙的森林游记
Description
暑假来了,绿纹龙很高兴。于是飘飘乎就来到了森林一日游。可是他却看到了很不和谐的一幕,一群猎人在森林里围捕小动物。森林可以看做是一个10*10的方格,如下图所示,1表示猎人,0表示小动物。
已知猎人保持不动,而小动物可以往上下左右任意方向逃脱(当然不能撞上猎人)。小动物可以逃出森林。但上图背景色被标红的那部分小动物将永远无法逃脱猎人的魔爪。
Input
一个10*10的矩阵,描述森林中猎人和小动物分布的情况。保证每个点要么为猎人,要么为小动物。
Output
一个整数,表示不能逃脱猎人魔爪的小动物数量。
Samples
Input
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
Output
15
# include<iostream>
# include<queue>
using namespace std;
struct node{int x;int y;
};
queue<node>q;int a[15][15],ans;
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x*f;
}
void bfs(int u,int v){q.push({u,v});while(!q.empty()){for(int i=0;i<4;i++){node x=q.front();int dx=xx[i]+x.x ;int dy=yy[i]+x.y;if(dx>=0&&dx<=11&&dy>=0&&dy<=11&&!a[dx][dy]){q.push({dx,dy});a[dx][dy]=1;}}q.pop();}
}
int main(){for(register int i=1;i<=10;++i)for(register int j=1;j<=10;++j)a[i][j]=read();bfs(0,0);for(register int i=1;i<=10;++i)for(register int j=1;j<=10;++j)if(a[i][j]==0) ans++;cout<<ans;return 0;
}
更多推荐
D. 1.绿纹龙的森林游记
发布评论