The 13th Zhejiang Provincial Collegiate Programming Contest

People Counting

Time Limit: 2 Seconds Memory Limit: 65536 KB

In a BG (dinner gathering) for ZJU ICPC team, the coaches wanted to count the number of people present at the BG. They did that by having the waitress take a photo for them. Everyone was in the photo and no one was completely blocked. Each person in the photo has the same posture. After some preprocessing, the photo was converted into a H×W character matrix, with the background represented by ".". Thus a person in this photo is represented by the diagram in the following three lines:

.O.
/|
(.)

Given the character matrix, the coaches want you to count the number of people in the photo. Note that if someone is partly blocked in the photo, only part of the above diagram will be presented in the character matrix.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first contains two integers H, W (1 ≤ H, W ≤ 100) - as described above, followed by H lines, showing the matrix representation of the photo.

Output

For each test case, there should be a single line, containing an integer indicating the number of people from the photo.

Sample Input

2
3 3
.O.
/|
(.)
3 4
OOO(
/|\
()))

Sample Output

1 4

题意：给你一个H*W的矩阵问其中有多少个人（只要有一个人的身体的某一部分出现在矩阵中就算一个人）

.O.
/|
(.) 如图表示一个人

题解：1.二维map存图

2.先统计矩阵中的‘O’

3.当遇到某一身体部位时（除了头部）向上找到当前这个人的头部的位置若找到的位置不是‘O’ 则改写为‘O’ 并答案自增1 若是‘O’则说明这个人已经统计过

  1 #include<iostream>
  2  #include<cstring>
  3  #include<cstdio>
  4  #include<queue>
  5  #include<stack>
  6  #include<map>
  7  #include<set>
  8  #include<algorithm>
  9  #define LL __int64
 10  #define pi acos(-1.0)
 11  #define mod 1
 12  #define maxn 10000
 13  using namespace std;
 14  int t;
 15 map<int,map<int,char> > mp;
 16  int n,m;
 17  int main()
 18  {
 19      while(scanf("%d",&t)!=EOF)
 20      {
 21          for(int i=1;i<=t;i++)
 22          {
 23              scanf("%d %d",&n,&m);
 24              int ans=0;
 25              getchar();
 26              mp.clear();
 27              for(int j=1;j<=n;j++)
 28             {  
 29                  for(int k=1;k<=m;k++)
 30                  { 
 31               scanf("%c",&mp[j][k]);
 32                   if(mp[j][k]=='O')
 33                     ans++;
 34              }
 35                  getchar();
 36            }
 37           for(int j=1;j<=n;j++)
 38          {
 39            for(int k=1;k<=m;k++)
 40           { 
 41               int flag=0;
 42              if(mp[j][k]=='O')
 43                  flag=0;
 44              if(mp[j][k]=='/')
 45             {
 46                 if(mp[j-1][k+1]=='O')
 47                    flag=0;
 48                 else
 49                 {
 50                     flag=1;
 51                     mp[j-1][k+1]='O';
 52                 }
 53             } 
 54            if(mp[j][k]=='|')
 55             {
 56                 if(mp[j-1][k]=='O')
 57                    flag=0;
 58                 else
 59                 {
 60                     flag=1;
 61                     mp[j-1][k]='O';
 62                 }
 63             } 
 64             if (mp[j][k]=='\')
 65             {
 66                 if(mp[j-1][k-1]=='O')
 67                    flag=0;
 68                 else
 69                 {
 70                     flag=1;
 71                     mp[j-1][k-1]='O';
 72                 }
 73             } 
 74             if(mp[j][k]=='(')
 75             {
 76                 if(mp[j-2][k+1]=='O')
 77                    flag=0;
 78                 else
 79                 {
 80                     flag=1;
 81                     mp[j-2][k+1]='O';
 82                 }
 83             } 
 84             
 85             if(mp[j][k]==')')
 86             {
 87                 if(mp[j-2][k-1]=='O')
 88                    flag=0;
 89                 else
 90                 {
 91                     flag=1;
 92                     mp[j-2][k-1]='O';
 93                 }
 94             } 
 95             if(flag)
 96              ans++;
 97           }
 98           }
 99           cout<<ans<<endl;
100         }
101      }
102      return 0;
103  }