C.S.I.: P15

Time Limit: 1000 ms Memory Limit: 65535 kB Solved: 23 Tried: 249

Submit

Status

Best Solution

Back

Description

 

You have been cast as the computer genius hero-of-the-day for the season finale 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 five 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 defined 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 first 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

 

Source

 

IDI Open 2013 Programming Contest

模拟+深搜

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define LL long long#define ULL unsigned long long#define UINT unsigned int#define MAX_INT 0x7fffffff#define MAX_LL 0x7fffffffffffffff#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))#define MAXN 33char g[MAXN][MAXN];//const char ok[]={'|', '/', '\\', '-', '@'};const int dx[]={-1, -1, -1, 0, 0, 1, 1, 1}, dy[]={0, -1, 1, -1, 1, -1, 0, 1};int w, h, birds, flo;bool vis[MAXN][MAXN];bool cango(int x, int y){ if(x<0 || y<0 || x>h-2 || y>w-1 || g[x][y]=='.' || vis[x][y]) return false; return true;}void dfs(int x, int y){ vis[x][y]=true; for(int i=0; i<8; i++){ int tx=x+dx[i], ty=y+dy[i]; if(cango(tx, ty)) dfs(tx, ty); }}bool ok_lft(int x, int y){ return y<0 || g[x][y]=='.';}bool ok_rit(int x, int y){ return y>=w || g[x][y]=='.';}bool ok_up(int x, int y){ if(x<0) return true; for(int k=0; k<6 && y
             
              -1; k++, y--) if(g[x][y]!='.') return false; return true;}bool ok_down(int x, int y){ for(int k=0; k<6 && y
              
               -1; k++, y--) if(g[x][y]!='.') return false; return true;}bool isbird(int x, int y){ if(ok_lft(x, y-4) && ok_rit(x, y+1) && ok_up(x-1, y+1) && ok_down(x+1, y+1)) return true; return false;}int main(){// freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin); int T; scanf(" %d", &T); while(T--){ int i, j; scanf(" %d %d", &h, &w); getchar(); for(i=0; i
               
                =4 && !vis[i][j]){ string t; for(int q=0; q<4 && !vis[i][j]; q++, j++) t+=g[i][j]; if(t==bid && isbird(i, j-1)) birds++; } printf("Flowers: %d\nBirds: %d\n", flo, birds); } return 0;}