B-Little Pigs and Wolves
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Once upon a time there were several little pigs and several wolves on a two-dimensional
grid of size n × m. Each cell in this grid was either empty, containing one little pig, or
containing one wolf.
A little pig and a wolf are adjacent if the cells that they are located at share a side. The
little pigs are afraid of wolves, so there will be at most one wolf adjacent to each little pig.
But each wolf may be adjacent to any number of little pigs.
They have been living peacefully for several years. But today the wolves got hungry. One
by one, each wolf will choose one of the little pigs adjacent to it (if any), and eats the poor
little pig. This process is not repeated. That is, each wolf will get to eat at most one little
pig. Once a little pig gets eaten, it disappears and cannot be eaten by any other wolf.
What is the maximum number of little pigs that may be eaten by the wolves?
Input
The first line contains integers n and m (1 ≤ n, m ≤ 10) which denotes the number of
rows and columns in our two-dimensional grid, respectively. Then follow n lines
containing m characters each — that is the grid description. "." means that this cell is
empty. "P" means that this cell contains a little pig. "W" means that this cell contains a wolf.
It is guaranteed that there will be at most one wolf adjacent to any little pig.
Output
Print a single number — the maximal number of little pigs that may be eaten by the
wolves.
Sample test(s)
input
2 3
PPW
W.P
output
2
input
3 3
P.W
.P.
W.P
output
0
算法分析：待续！
代码：
#include <stdio.h>
#include <string.h>
char s[11][11];
int f[11][11];
int g[11][11];
int cnt;
int n,m;
void bfs(int dd, int ff )
{
if( dd-1>=0 )
{
if(s[dd-1][ff]=='P' )
{
f[dd-1][ff] ++;
g[dd][ff]=1;
}
}
if(ff-1>=0)
{
if(s[dd][ff-1]=='P' )
{
f[dd][ff-1] ++;
g[dd][ff]=1;
}
}
if(dd+1<n )
{
if(s[dd+1][ff]=='P' )
{
f[dd+1][ff] ++;
g[dd][ff]=1;
}
}
if(ff+1<m)
{
if(s[dd][ff+1]=='P' )
{
f[dd][ff+1] ++;
g[dd][ff]=1;
}
}
}
char ch;
int main()
{
int i, j, cc;
while(scanf("%d %d%*c", &n, &m) !=EOF )
{
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
ch=getchar();
while(ch!='W' && ch!='P' && ch!='.' )
{
ch=getchar();
}
s[i][j] = ch;
}
}
memset(f, 0, sizeof(f) );
memset(g, 0, sizeof(g));
cnt=0;
cc=0;
for(i=0; i<n; i++)
{
for(j=0; j<m; j++ )
{
if(s[i][j] == 'W' )
{
bfs(i, j) ;
}
}
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(g[i][j]==1)
cc++;
}
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(f[i][j]>0)
cnt++;
}
}
if(cnt >= cc)
printf("%d
", cc );
else
printf("%d
", cnt );
}
return 0;
}