绿纹龙的森林游记——UPC

游记——UPC"/>

绿纹龙的森林游记——UPC

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

已知猎人保持不动，而小动物可以往上下左右任意方向逃脱（当然不能撞上猎人）。小动物可以逃出森林。但上图背景色被标红的那部分小动物将永远无法逃脱猎人的魔爪。
输入
一个10*10的矩阵，描述森林中猎人和小动物分布的情况。保证每个点要么为猎人，要么为小动物。
输出
一个整数，表示不能逃脱猎人魔爪的小动物数量。
样例输入 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

样例输出 Copy
15

写dfs进行搜索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
#define read read()
const ll inf = 1e15;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
ll num[maxn];
ll searc[100][100];
void dfs(int a,int b){if(a>=1&&a<=10&&b>=1&&b<=10&&!searc[a][b]){searc[a][b]=1;dfs(a+1,b);dfs(a-1,b);dfs(a,b+1);dfs(a,b-1);}return ;
}
int main(){for(int i=1;i<=10;i++)for(int j=1;j<=10;j++)searc[i][j]=read;for(int i=1;i<=10;i++){dfs(1,i);dfs(i,1);dfs(10,i);dfs(i,10);}ll ans=0;for(int i=1;i<=10;i++)for(int j=1;j<=10;j++)if(!searc[i][j])ans++;cout<<ans<<endl;return 0;
}