1 solutions
Information
- ID
- 777
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 4
- Tags
- # Submissions
- 35
- Accepted
- 17
- Uploaded By
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;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.