Count how many wolves can eat pigs on a small grid by checking adjacent cells.
Problem
You are given a 2D grid made of three kinds of cells:
'.'— empty cell'P'— a pig'W'— a wolf
A wolf can eat a pig if they are in adjacent cells, horizontally or vertically. Each wolf can eat at most one pig, and each pig can be eaten by at most one wolf.
Find the maximum number of pigs that can be eaten.
Goal
Choose pairings between neighboring wolves and pigs so that the number of eaten pigs is as large as possible.
Input Format
- The input is a grid of characters.
- Each cell is one of
'.','P', or'W'. - Adjacency is 4-directional: up, down, left, right.
Output Format
- Output a single integer: the maximum number of pigs that can be eaten.
Constraints
- The grid is finite.
- Each wolf and pig can participate in at most one pairing.
- Only orthogonally adjacent cells may be paired.
Example 1
Input
3 3 P.W .W. P.P
Output
2
Explanation
The wolf in the top row can eat the pig to its left or right, and the bottom wolf can eat one of the remaining adjacent pigs. In total, 2 pigs can be eaten.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.