The Pied Piper
Time limit1sMemory limit256 MB
Place the fewest cells so every frozen walk under the U/D/L/R map enters a safe cell; model directed functional reverse graphs and find a minimum set of path-starting states.
- Level
Hard8 of 10
- Topics
- Graph, Simulation, Greedy, Dynamic programming
- Solved
- No attempts yet
Problem
Seongwoo, the Pied Piper, plays his pipe again today.
When Seongwoo plays the pipe, the Yeongwail members start moving in the directions he has set without realizing it. He sets one of four directions: U, D, L, R, which make them move up, down, left, and right respectively.
Jaehoon watches this and, to protect the Yeongwail members who can no longer bear to move, decides to build a state-of-the-art soundproof facility called a 'SAFE ZONE' at certain spots so the members cannot hear Seongwoo's pipe. Since his budget is limited, Jaehoon analyzes the directions Seongwoo has set and wants to build the minimum number of 'SAFE ZONEs'.
Given the direction map Seongwoo has set, write a program that helps Jaehoon and outputs the minimum number of 'SAFE ZONEs' such that the Yeongwail members can enter a 'SAFE ZONE' when Seongwoo plays the pipe, no matter where on the map they are.
Input
The first line gives N (1 ≤ N ≤ 1,000), the number of rows of the map, and M (1 ≤ M ≤ 1,000), the number of columns.
From the second line, N lines follow, each a string of length M giving the map.
No direction pointing off the map is given.
Output
On the first line, output the minimum number of 'SAFE ZONEs'.