codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

116B.md (1978B)


      1 Source: https://codeforces.com/problemset/problem/116/B
      2 
      3 B. Little Pigs and Wolves
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 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.
     22 
     23 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.
     24 
     25 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.
     26 
     27 What is the maximum number of little pigs that may be eaten by the wolves?
     28 
     29 Input
     30 
     31 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.
     32 
     33 It is guaranteed that there will be at most one wolf adjacent to any little pig.
     34 
     35 Output
     36 
     37 Print a single number — the maximal number of little pigs that may be eaten by the wolves.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2 3  
     45 PPW  
     46 W.P
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 3 3  
     59 P.W  
     60 .P.  
     61 W.P
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 0
     68 ```
     69 
     70 Note
     71 
     72 In the first example, one possible scenario in which two little pigs get eaten by the wolves is as follows.
     73 
     74  ![](https://espresso.codeforces.com/10c56d3cfe5fe9463b4a9bc0c4fac5ec5dca5e80.png)