题目描述
暑假来了，绿纹龙很高兴。于是飘飘乎就来到了森林一日游。
可是他却看到了很不和谐的一幕，一群猎人在森林里围捕小动物。
森林可以看做是一个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; }
