赞
踩
- #include <iostream>
- #include <iomanip>
- using namespace std;
- int a[110][110];
- char b[110][110];
- int n,m;
- int si,sj,ei,ej;
- int di[] = {0,1,0,-1};
- int dj[] = {1,0,-1,0};
- void aaa(int,int,int);
- int main()
- {
- while(true)
- {
- cin>>n>>m;
- if(n==0&&m==0) break;
- for(int i = 0;i<n;i++)
- {
- for(int j = 0;j<m;j++)
- {
- cin>>b[i][j];
- if(b[i][j]!='#')
- {
- a[i][j] = 1000000;
- }
- else{
- a[i][j] = 0;
- }
- if(b[i][j]=='@')
- {
- si = i;
- sj = j;
- }
- else if(b[i][j]=='*')
- {
- ei = i;
- ej = j;
- }
- }
- }
- aaa(si,sj,0);
- if(a[ei][ej]<100000)
- {
- cout<<a[ei][ej]<<endl;
- }
- else{
- cout<<-1<<endl;
- }
- }
- return 0;
- }
- void aaa(int i,int j,int cnt)
- {
- a[i][j] = cnt;
- for(int qqq = 0;qqq<4;qqq++)
- {
- int ti = i+di[qqq];
- int tj = j+dj[qqq];
- if(ti>=0&&ti<n&&tj>=0&&tj<m&&a[ti][tj]>cnt+1&&b[ti][tj]!='#')
- {
- aaa(ti,tj,cnt+1);
-
- }
- }
-
- return;
- }
农夫约翰总是想要一个农场的地图,所以他拍摄了一张N行M列的卫星照片。 一部分的照片看起来像这样: 他认为每个联通块都是一个谷仓或一头奶牛。 农夫约翰认为一个联通块是谷仓,当且仅当它是一个完整的矩形,否则该联通块是一头奶牛。
在下面的照片中,有三个谷仓(大小分别为2x1,2x5和1x1)和两头奶牛。 计算他的卫星照片中谷仓和奶牛的数量。
. . . . . . . . . . . . . . . . . .
. . # # # # # . . . . . . . # # . .
. . # # # # # . . . . . . # # . . .
. . . . . . . . . . . . . . . . . .
# . . . . . . . # # # . . . . . # .
# . . . . . # # # # # . . . . . . .
输入
行1:两个空格分隔的整数:N和M
行2..N + 1:行i + 1表示照片的行i包含M个字 符(且不含空格)。
输出
行1:照片中的谷仓数量。
行2:照片中的奶牛数量。
- #include <iostream>
- #include <iomanip>
- using namespace std;
- int a[110][110];
- char b[110][110];
- int n,m;
- int si,sj,ei,ej;
- int di[] = {0,1,0,-1};
- int dj[] = {1,0,-1,0};
- int ck = 0,nn = 0;
- int cnt = 0;
- void aaa(int,int);
- int main()
- {
- cin>>n>>m;
- for(int i = 0;i<n;i++)
- {
- for(int j = 0;j<m;j++)
- {
- cin>>b[i][j];
- }
- }
- for(int i = 0;i<n;i++)
- {
- for(int j = 0;j<m;j++)
- {
- if(b[i][j]=='#')
- {
- si = i;
- ei = i;
- sj = j;
- ej = j;
- cnt = 0;
- aaa(i,j);
- if(cnt==(ei-si+1)*(ej-sj+1))
- {
- ck++;
- }
- else{
- nn++;
- }
- }
- }
- }
- cout<<ck<<endl<<nn;
- return 0;
- }
- void aaa(int i,int j)
- {
- b[i][j] = '.';
- cnt++;
- si = min(si,i);
- sj = min(sj,j);
- ei = max(ei,i);
- ej = max(ej,j);
- for(int qqq = 0;qqq<4;qqq++)
- {
- int ti = i+di[qqq];
- int tj = j+dj[qqq];
- if(ti>=0&&ti<n&&tj>=0&&tj<m&&b[ti][tj]=='#')
- {
- aaa(ti,tj);
-
- }
- }
-
- return;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。