z-transformer
After seeing the Transformers movie, Little Z decided to make his own transformer.
For start, he wants to make only 2D transformer, that is made of steel parts, and joints that connect different parts.
The description of the transformer can be represented by a 2D matrix in the following form:.aa0bb.
Where '.' represents a free space, the letters represent the steel parts (each letter represents the same part) and finally '0' (zero) represents a joint.
Each joint can move in 90 degrees increments. The transformer above can look transform to:.aa0
...b
...b
or ...b
...b
.aa0
But the following transformer can not transform at all (because of the way the parts are connected)0aa0
b..c
b..c
0dd0
Little Z wants to send the transformer to his friend, and wants to use the smallest box possible. So he wonders, what is the smallest (in terms of area) 2D box he can use, so that the whole transformer fits inside.
4 5
0a0..
b.d0e
0c0..
.....Output:
12Explanation: the transformers can have the following shape:
0a0e
b.d0
0c0.3 8
a.......
a..bb...
aa0bb0ccOutput:
12Explanation: the transformers can have the following shape:
cc0
abb
abb
aa01 17
.aaa0bb0cc0d0e0f.Output:
15Explanation: the transformers can have the following shape:
aaa0bb0cc0d0e0fSubmit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.