Given two contiguous shapes of the same area, determine the optimal way to divide the first shape into a minimum number of contiguous segments such that they can be rearranged to form the second shape. In other words, find the minimum number of segments required that can form both of the shapes.
"Contiguous" means that every square in the shape can be reached from any other square by walking across edges. Shapes and segments are allowed to have holes.
"Rearrange" means you move the segments around; you can translate, rotate, and reflect them.
The shapes are contained on a grid; in other words, each shape consists of a collection of unit squares joined by their corners/edges.
Input Specifications
The input will be provided in some reasonable format - list of points, array of strings representing each grid, etc. You can also take the sizes of the grid if requested. The grids will have the same dimensions and the two shapes are guaranteed to have the same area, and the area will be positive.
Output Specifications
The output should just be a single positive integer. Note that there will always be a positive answer because in the worst case scenario, you just divide the shapes into N
unit squares.
Examples
The examples are presented as a grid with .
representing a blank and #
representing part of the shape.
Case 1
Input
.....
.###.
.#.#.
.###.
.....
###..
..#..
..#..
..###
.....
Output
2
Explanation
You can divide it into two L-shaped blocks of 4:
#
###
Case 2
Input
#...
##..
.#..
.##.
.##.
####
....
....
Output
2
Explanation
You can split the shapes like so:
A...
AA..
.A.
.BB.
.AA.
BBAA
....
....
You could also do:
A...
AA..
.B..
.BB.
.AB.
AABB
....
....
Case 3
Input
#....#
######
.####.
.####.
Output
2
Explanation
A....B
AAABBB
.ABBB.
.AAAB.
(This test case demonstrates the necessity to rotate/reflect shapes for optimal output)
Case 4
Input
.###.
..#..
.##..
.##..
Output
2
Explanation
No matter how you select blocks, selecting a 2x1 from the first shape necessarily prevents the other two from being grouped together; thus, you can use one 2x1 and two 1x1s. However, (thanks @Jonah), you can split it into a 3-block L shape and a single square like so:
.AAB.
..A..
.AA..
.BA..
Case 5
Input
##
#.
#.
##
Output
1
Explanation
The input and output shapes may be identical.
Case 6
Input
#..
##.
.##
#####
Output
3
Explanation
There is no way to divide the original shape into two pieces such that both pieces are straight, so at least three are needed.