1 solutions
-
0
1、通过一个连通‘#’区域内 x 的最大值与最小值,确定矩阵的一条边长,连通‘#’区域内 y 的最大值与最小值确定矩阵的另一条边长。 2、两边相乘就可以得到连通‘#’的最大矩阵。 3、最后再判断一下,连通的‘#’的数量是否等于矩阵的大小,等于为谷仓,否则为奶牛。
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> #include <string.h> #include <queue> #include <stack> #include <map> #include <set> #include <vector> using namespace std; #define ll long long int n,m,mix,miy,mas,may,cow,farm,temp; char a[100][100]; int vis[100][100]; int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0}; void dfs(int x,int y) { vis[x][y]=1; temp++; mix=min(mix,x); miy=min(miy,y); mas=max(mas,x); may=max(may,y); for(int i=0; i<4; i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx>=0&&ty>=0&&tx<n&&ty<m&&!vis[tx][ty]&&a[tx][ty]=='#') { dfs(tx,ty); } } } int main() { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { scanf("%s",&a[i]); } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { mix=100,miy=100,mas=0,may=0; if(!vis[i][j]&&a[i][j]=='#') { temp=0; dfs(i,j); int k=(1+mas-mix)*(1+may-miy); if(k==temp) { farm++; } else { cow++; } } } } cout<<farm<<endl; cout<<cow<<endl; return 0; }
- 1
Information
- ID
- 777
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 4
- Tags
- # Submissions
- 35
- Accepted
- 17
- Uploaded By