The school cafeteria floor at RHHS can be modelled as an by grid bounded by walls on all sides. Initially, each cell in the grid is either dry (denoted by
.) or wet (denoted by
W). The cafeteria is considered safe if it is impossible for a student starting at any dry location to walk to any wet location. Students only know how to walk up, down, left and right, and cannot walk through safety cones (denoted by
C) or walls.
As the janitor, you have an unlimited supply of safety cones and it is your task to place the safety cones to ensure that the cafeteria is safe. You can only place safety cones on dry locations and you must also use the least number of cones possible.
What does the cafeteria look like after you have finished your task?
For all subtasks:
|Points Awarded||Additional Constraints|
The first line of input contains two integers and .
The next lines each contain a string of characters consisting of only
W characters, denoting the grid.
Output the grid after placing the cones optimally.
5 6 .W.... ...... ..WW.. ...W.. ......
CWC... .CCC.. .CWWC. ..CWC. ...C..