Legendary Dango Maker 4
Time limit1sMemory limit512 MB
Given an R by C grid of P, W, and G dangos, find the maximum number of non-overlapping three-cell lines that read P-W-G or G-W-P.
- Level
Medium7 of 10
- Topics
- Matrix, Graph, Implementation
- Solved
- No attempts yet
Problem
You are a professional who makes rice dumplings called dangos. You are now skewering dangos onto sticks.
The dangos are placed in a rectangular grid with R rows and C columns. Each cell contains exactly one dango. The color of a dango is pink (P), white (W), or green (G). You choose three consecutive cells in one of four directions: vertical (top to bottom), horizontal (left to right), or diagonal (left-top to right-bottom, or right-top to left-bottom). Then you take the three dangos from these cells, starting from one end and moving to the other, and skewer them in order onto a stick to make a stick of dangos. For example, if you choose three consecutive cells vertically, you can take the dangos from top, middle, bottom, or from bottom, middle, top, in that order. You cannot take them in the order middle, bottom, top, or bottom, top, middle. You cannot skewer a dango onto more than one stick.
A stick of dangos is beautiful if its colors, in order, are pink-white-green or green-white-pink.
What is the maximum number of beautiful sticks of dangos you can make?
Input
The input is given in the following format.
R C
D1
.
.
.
DR
Di (1 to R) is a string of length C consisting of P, W, and G. The j-th character of Di is the color of the dango in the cell in the i-th row from the top and the j-th column from the left.
Output
Print R lines. Each line has C characters. The j-th character of the i-th line is one of the following.
|if you make a beautiful stick using that cell, the cell directly above it, and the cell directly below it.-if you make a beautiful stick using that cell, the cell to its left, and the cell to its right.\\if you make a beautiful stick using that cell, the cell left above it, and the cell right below it./if you make a beautiful stick using that cell, the cell right above it, and the cell left below it.- Otherwise,
P,W, orG, the same as the color of the dango in that cell in the input.
Constraints
- 3 ≤ R ≤ 500
- 3 ≤ C ≤ 500
- Di (1 to R) is a string of length C consisting of P, W, and G.