PaintTheRoom
SRM 668 · 2015-08-31 · by zxqfl
SRM 668 · 2015-08-31 · by zxqfl · Graph Theory, Simple Math
Problem Statement
Problem Statement
Little Liz stepped in a bucket of green paint. Now she leaves green footprints wherever she walks. Fortunately, her school just built a new room which is supposed to have a green floor. Making the best of the situation, her teacher told her to paint the room by walking on its floor.
The floor is a grid of cells with R rows and C columns. Little Liz occupies a position in this grid. She can move up, down, left, or right. (She cannot move diagonally.) To ensure that each cell gets the appropriate amount of paint, Liz should visit each cell exactly K times. Liz visits a cell whenever she moves into it. Liz also visits a cell if she begins her walk on it. Liz can begin and end on any cell.
If it is possible to paint the room in the required way, return "Paint". Otherwise, return "Cannot paint". (All quotes are for clarity only.)
The floor is a grid of cells with R rows and C columns. Little Liz occupies a position in this grid. She can move up, down, left, or right. (She cannot move diagonally.) To ensure that each cell gets the appropriate amount of paint, Liz should visit each cell exactly K times. Liz visits a cell whenever she moves into it. Liz also visits a cell if she begins her walk on it. Liz can begin and end on any cell.
If it is possible to paint the room in the required way, return "Paint". Otherwise, return "Cannot paint". (All quotes are for clarity only.)
Constraints
- R will be between 1 and 50, inclusive.
- C will be between 1 and 50, inclusive.
- K will be between 1 and 50, inclusive.
Examples
0)
1 1 1 Returns: "Paint"
There is only one cell in this grid. By starting on the cell, Little Liz visits it once.
1)
1 1 2 Returns: "Cannot paint"
This is the same case as Example 0, but now the cell must be visited twice. This is impossible.
2)
1 2 2 Returns: "Paint"
There are two cells, and they are in the same row. One possible solution is to start on the left cell, then move right, then left, then right. This visits each cell twice, as required.
3)
2 2 3 Returns: "Paint"
4)
1 1 1 Returns: "Paint"
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PaintTheRoom with a public method string canPaintEvenly(int R, int C, int K) · 94 test cases · 2 s / 256 MB per case