CODEWITHSUNDEEP
calgorithmdata-structuresmultidimensional-arrayshapes
Aragon
Aragon

Reputation: 1551

Given 2D array with marked cells, find duplicate shapes formed by those marked cells

Given a 2D array with cells which are marked and combined together forms different linear shapes, how would you identify duplicate shapes.

0010000100000000000000000000
0010000100000000000000000000
0011100100000100000000011100
0000000100000111111000000000
0010000111100100000000000000
0110000000000001111000000000
0010000100000000000000000111
0000000001000000000011110000
0000000001111110000000000000
0010000001000000000000000000

Here we have 3 duplicate shapes :
1
111111
1

111

1

Upvotes: 0

Views: 131

Answers (1)

Nick Larsen
Nick Larsen

Reputation: 18877

Find all the shapes generated by connected 1s by looping over the cells until you find a 1 and then use a flood fill algorithm to find the shape formed by all connected cells. How you store the flood filled shape is up to you, but I'll assume you created a string representation of each one. Now find the distinct strings using any of the jillions of methods that are out there for comparing strings.

Upvotes: 3

Related Questions