Cheerio Contest 3 P1 - Wet Floor

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

The school cafeteria floor at RHHS can be modelled as an N by M 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?

Constraints

For all subtasks:

  • 1 \le N, M \le 10^3
Points Awarded Additional Constraints
5 points N = 1
10 points None

Input Specification

The first line of input contains two integers N and M.

The next N lines each contain a string of M characters consisting of only . and W characters, denoting the grid.

Output Specification

Output the grid after placing the cones optimally.

Sample Input

5 6
.W....
......
..WW..
...W..
......

Sample Output

CWC...
.CCC..
.CWWC.
..CWC.
...C..

Comments

There are no comments at the moment.