Loading...
Loading...
Loading...
Kiran's lake map is a grid of r rows and c columns, with 1 for land and 0 for water. Land cells that share a side form an island.
Two islands have the same shape if you can slide one onto the other, moving it only up, down, left or right, so that the land cells match exactly. Turning or flipping is not allowed, so an L and a mirrored L are different shapes.
Print the number of different island shapes on the map.
1 or 0, with no spaces.1 or 0.Example 1
Input
4 5 11011 10000 00001 11011
Output
3
The two flat pairs share a shape. The two L shapes are mirror images, so they differ. That makes 3 shapes.
Example 2
Input
3 3 101 000 101
Output
1
Four single cells, all the same shape.
Try the problem first. Open one hint at a time.
First find each island as usual, by visiting all land cells joined to a starting cell.
Describe an island by the positions of its cells relative to its starting cell: for each cell store (row − startRow, col − startCol).
If you always start an island at its first cell in a row-by-row scan and visit cells in a fixed order, the same shape always gives the same list.
Turn each list into a string and put it in a HashSet. The size of the set is the answer.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor