You have been cast as the computer genius hero-of-the-day for the season fi nale of the show C.S.I.: P15 (coming this fall). Somewhat unsurprisingly,there is that camera feed that needs to be analyzed. The camera in question is recording pictures in HD-9000
quality with extra regression and the stream is then internally matched by a re-inverted isomorphic bit coefficient matrix, then plasma shifted fi ve times for good measure. You then view the feed through Netscape Navigator 4 Platinum Edition. (Note that
"internally" is just fancy talk for "inside the camera".)
Unfortunately, a saboteur turned on ASCII mode on the camera and set the camera in picture burst mode. So now all you have is a bunch of still ASCII images. And now,for reasons that will be revealed later in the show, you are to design and implement a deterministic
algorithm for counting the number of flowers and birds in a given still image.
The pictures always include the ground,which will show up as a contiguous row of '=' characters. The ground will always be the bottom-most row of "ASCII pixels". There will never be anything else on that row (though, on one of the pictures taken before the
sabotage there is a stray electron that a someone will accidentally nd by zooming in too far, but that is for a later episode).
Air is marked in the feed as a '.' (a dot). The ground is the last line of the feed, and it looks like this: '==========='. A flower is defi ned as any 8-connected component which consists of characters from the set { '|', '/', '\', '-', '@'}, and which is
also connected to the ground. Two cells belong to the same 8-connected component if there is a path between them that goes through elements from the forementioned set only, such that each step in the path is to an 8-connected neighbour (horizontally, vertically,
or diagonally adjacent cell). A bird is an occurence of '/\/\', such that all neighbouring cells are either air or edges of the image. So if you see something that looks like a bird on the ground, it is a flower (possibly an ex-parrot, but that is also a flower
for our purposes).
Input
The fi rst line of the input consists of a single integer T, the number of test cases. Each of the following T cases then begins with a line of two integers separated by a space,the height H and width W, and ends with H lines describing the picture. Each
line of the picture has exactly W characters. All lines but the last consist of only the following characters: { '.', '|', '/', '\', '-', '@'}. The last line consists of '=' characters only.
0 < T <= 100
0 < W <= 30
0 < H <= 30
Output
For each test case, output two lines. If the number of flowers is F and the number of birds is B, the output should read
Flowers: F
Birds: B
Sample Input
1
12 28
............................
............................
\@/.../\/\..../\/\..........
.|..........................
.|....\@/.........../\/\....
.|.....|.............|......
.|.....|.............|......
.|.....|..\@/....\@/.|......
.|.....|....\..../...|.|-|..
.|.....|.....\../....|.|.|..
.|.....|......\/.....|.|.|..
============================
Sample Output
Flowers: 5
Birds: 2
一道模拟题，要统计相片中花与鸟的个数
一朵花必须是除了空气的任意符号组成，而且必须连在地上
鸟必须是/\/\并且四周都是空气
dfs找出所有的花，再枚举所有的鸟即可
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char map[35][35];
int vis[35][35],h,w;
int xx[10] = {1,1,1,-1,-1,-1,0,0};
int yy[10] = {-1,0,1,-1,0,1,1,-1};
void dfs(int x,int y)
{
int i;
if((map[x][y]!='|'&&map[x][y]!='/'&&map[x][y]!='\\'&&map[x][y]!='-'&&map[x][y]!='@')||vis[x][y]==1)//非花的一部分或者已经访问过
return ;
vis[x][y] = 1;
for(i = 0; i<8; i++)
dfs(x+xx[i],y+yy[i]);
}
int main()
{
int n,i,j,flower,bird;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&h,&w);
memset(map,'.',sizeof(map));
memset(vis,0,sizeof(vis));
for(i = 1; i<=h; i++)
{
getchar();
for(j = 1; j<=w; j++)
{
scanf("%c",&map[i][j]);
}
}
flower = bird = 0;
for(i = 1; i<=w; i++)//从地面开始网上枚举
{
if((map[h-1][i] == '-' || map[h-1][i] == '\\' || map[h-1][i] == '/' || map[h-1][i] == '|' || map[h-1][i] == '@') && vis[h-1][i]==0)//是花的一部分并且没有访问过
{
dfs(h-1,i);
flower++;
}
}
for(i = 1; i<=h; i++)//找出鸟
{
for(j = 1; j<=w; j++)
{
if(map[i][j] == '/' && map[i][j+1] == '\\' && map[i][j+2] == '/' && map[i][j+3] == '\\')
{
if(map[i-1][j-1] == '.' && map[i-1][j] == '.' && map[i-1][j+1] == '.' && map[i-1][j+2] == '.' && map[i-1][j+3] == '.' && map[i-1][j+4] == '.')
{
if(map[i][j-1] == '.' && map[i][j+4] == '.')
{
if(map[i+1][j-1] == '.' && map[i+1][j] == '.' && map[i+1][j+1] == '.' && map[i+1][j+2] == '.' && map[i+1][j+3] == '.' && map[i+1][j+4] == '.')
{
bird++;
}
}
}
}
}
}
printf("Flowers: %d\nBirds: %d\n",flower,bird);
}
return 0;
}