Crocodiles

Time limit2sMemory limit1024 MB

Summary

Given a grid of crocodiles that each face a direction, find the most crocodiles that can leave the pool when Klas wakes them one at a time.

Level: Medium7 of 10
Topics: Graph, Shortest path, Simulation
Solved: No attempts yet

Statement

On his trip through Australia, Klas has started running low on money. Luckily, he found a very good side job: chasing crocodiles out of people's gardens. His first job is a swimming pool that can be represented as an $N \times M$ grid, where each cell is either empty or contains a sleeping crocodile. Each sleeping crocodile faces one of the four compass directions. Klas can wake a crocodile by throwing an apple at it. An awake crocodile swims very fast in the direction it faces, until it either leaves the pool or crashes into another crocodile. If two crocodiles crash, both become very angry, and there is a high risk that they attack Klas.

Your task is to compute how many crocodiles Klas can get out of the pool if he throws apples in an optimal way. Two crocodiles may not crash. Klas can throw only one apple at a time, and the crocodiles swim so fast that he cannot throw the next apple until the previous crocodile has finished moving.

Examples3

Example 1
Input
```
1 5
WN.SE
```
Expected output
```
4
```
Example 2
Input
```
1 3
E.W
```
Expected output
```
0
```
Example 3
Input
```
3 4
.N.W
WWSS
EWEW
```
Expected output
```
4
```