D. 1.绿纹龙的森林游记 [ Problem 4398 ] [ Discussion ]

D. 1.绿纹龙的森林游记 [ Problem 4398 ] [ Discussion ]
Description
暑假来了，绿纹龙很高兴。于是飘飘乎就来到了森林一日游。可是他却看到了很不和谐的一幕，一群猎人在森林里围捕小动物。森林可以看做是一个10*10的方格，如下图所示，1表示猎人，0表示小动物。

已知猎人保持不动，而小动物可以往上下左右任意方向逃脱（当然不能撞上猎人）。小动物可以逃出森林。但上图背景色被标红的那部分小动物将永远无法逃脱猎人的魔爪。

Input
一个10*10的矩阵，描述森林中猎人和小动物分布的情况。保证每个点要么为猎人，要么为小动物。

Output
一个整数，表示不能逃脱猎人魔爪的小动物数量。

Samples
Input Copy
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

思路
从四条边每一个边的每一个点开始
这都是出口
除了出口是1

那么只需要从出口模拟接下来走的路线都可以了

走过的就不用再走了

#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
ll read(){
    ll res = 0, ch, flag = 0;if((ch = getchar()) == '-')flag = 1;else if(ch >= '0' && ch <= '9')res = ch - '0';while((ch = getchar()) >= '0' && ch <= '9' )res = res * 10 + ch - '0';return flag ? -res : res;}
const int maxn =1e6+199 ;
ll sum=0,maxa=-1;
ll n,m,k,w,ans=0,cnt=0;
ll a[300][300];
ll b[300][300];
ll dis[4][2]={
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};
ll mod=1e9+7;
struct node{
    int x,y;
}st,en;
queue<node>p;
void bfs(int x,int y)  //作用 遍历下一个位置并标记1 如果是1那么continue
{
    st.x=x;st.y=y;p.push(st);while(!p.empty()){
    st=p.front();p.pop();a[st.x][st.y]=1;for(int i=0;i<=3;i++){
    en.x=st.x+dis[i][0];en.y=st.y+dis[i][1];if(en.x<1||en.y<1||en.x>10||en.y>10||a[en.x][en.y])continue;a[en.x][en.y]=1;p.push(en);}}}
int main()
{
    for(int i=1;i<=10;i++){
    for(int j=1;j<=10;j++)cin>>a[i][j];}for(int i=1;i<=10;i++){
    if(!a[1][i]) //如果是出口就沿着出口找 能活下来的标记bfs(1,i);if(!a[i][1])bfs(i,1);if(!a[i][10])bfs(i,10);if(!a[10][i])bfs(10,i);}for(int i=1;i<=10;i++){
    for(int j=1;j<=10;j++)if(a[i][j]==0)cnt++;}cout<<cnt;return 0;
}