Temporary Editorial. Note that this is only one possible solution.

Traversing through the grid can be done with either BFS or DFS. The idea is to first iterate over the grid and run BFS/DFS on any point which is # and not yet visited. This will cover all # characters which represent one shape. When running BFS/DFS on this point, it is necessary to keep track of both the smallest and largest values encountered for both the x and the y coordinates. It is also necessary to keep track of the total area covered. Assuming that the shape is a rectangle at this location, these values can be used to calculate the top left, top right, bottom left and bottom right points of the rectangle.

There are two conditions to confirm the existence of a rectangle at this location:

1. The calculated corners of the rectangle are # characters, meaning the corners exist where they are supposed to be.
2. The area covered by the BFS/DFS is equal to the supposed area of the rectangle. The coordinates of the corners can be used for this purpose as well.

If these two conditions are met, then the shape is a rectangle.

Example:

  0 1 2
0 # # #
1 # # #
2 #   #

Calculated Values

Max x value: 2
Max y value: 2
Min x value: 0
Min y value: 0
Calculated Corners: (0,0),(2,0),(0,2),(2,2)
Calculated Area: ((2-0)+1)*((2-0)+1) = 3*3 = 9