Problem I
Three Little Kittens
The three little kittens, they lost their mittens,
And they began to cry,
"Oh, mother dear, we sadly fear,
That we have lost our mittens."
"What! Lost your mittens, you naughty kittens!
Then you shall have no pie."
"Meow, meow, meow."
"Then you shall have no pie."The three little kittens, they found their mittens,
And they began to cry,
"Oh, mother dear, see here, see here,
For we have found our mittens."
"Put on your mittens, you silly kittens,
And you shall have some pie."
"Purr, purr, purr,
Oh, let us have some pie."The three little kittens put on their mittens,
And soon ate up the pie,
"Oh, mother dear, we greatly fear,
That we have soiled our mittens."
"What, soiled your mittens, you naughty kittens!"
Then they began to sigh,
"Meow, meow, meow,"
Then they began to sigh.The three little kittens, they washed their mittens,
And hung them out to dry,
"Oh, mother dear, do you not hear,
That we have washed our mittens?"
"What, washed your mittens, then you’re good kittens,
But I smell a rat close by."
"Meow, meow, meow,
We smell a rat close by."
For this problem we want you to help the kittens find their mittens. Here is what we know: The kittens were playing in the snow. They were wearing little hoodies and had little booties on their hind paws and little mittens on the front paws. The mittens were attached by ribbons strung through the arms of the hoodies. The first kitten had red mittens; the second had green mittens, and the third had blue mittens, all with matching ribbons. But the mittens had gotten wet so the kittens pulled them off and out of their hoodies. You should be able to find them still attached by their ribbons strewn on the white snow.
You will be provided with a picture (array) of a rectangular yard with ’W’ marking snow, ’R’ marking the red mittens and ribbon, ’G’ for the green ones, and ’B’ for the blue ones. You will know you have found a red mitten if you find an ’R’ with only one other ’R’ among the (at most 8) neighboring cells of the array. You will know you have found part of the red ribbon if you find an ’R’ with two neighboring cells containing an ’R’. You may assume that there will never be more than 3 mutually adjacent bits of ribbon (a triangle). This means that if you trace a length of ribbon as though it were a path in a maze, you never have to choose among branches. There will always be at least one length of ribbon attaching a pair of mittens. The same idea applies for the green and blue mittens.
Input
There will be multiple lines of input, the first indicating the number of rows (1-20), the second indicating the number of columns (1-20), and the remaining lines presenting the picture of the yard, row by row, each row consisting of a string of ’W’, ’R’, ’G’, and ’B’ letters representing the color of each cell, column by column.
Output
Print three lines, one for the red mittens, one for the green, and one for the blue. Each line should have three row - column sets of coordinates representing the leftmost top occurrence of a ribbon/mitten, the leftmost top location of a mitten, and the location of the remaining mitten.
Sample Input 1 | Sample Output 1 |
---|---|
11 10 WWWWWWWWWW WWWWWRWWWW WWWWRWRRWW WWWRWWWWRW WWWWWWWRWW WWBBWWRWWW WBGGBRWWWW RGBWRBWWWW GWBWRWBBBW GWBRWWWWWB WGWWWWWWWB |
2 6 4 4 10 4 7 3 7 4 11 2 6 3 10 3 11 10 |
Sample Input 2 | Sample Output 2 |
---|---|
10 11 WWWWWWWWWBB WWWRWWWWBWW WWRWRWWWBWW WWRWWRWWBWW WRWWWWRBWWW WWRWWWBRRWW WWWRWBGWWRW WWWWWBGBBBW WWWWWWBGWWG WWWWWWWRGGW |
2 4 7 4 7 10 7 7 7 7 9 11 1 10 1 11 8 10 |