-1

I'm having a bit of difficulty by solving an exercise, hope I can get some help from you. Given a 2D Array with N rows and M columns, and the array has only elements with the value 0 and 1. Find the largest surface that is similar to a chessboard(where 0 are the white squares and 1 the black squares) and print the size of the surface(number of squares).

Constraints: 2<=N<=1000 2<=M<=1000

Example: N=4, M=5

0 1 1 0 1
1 0 1 0 1
0 0 1 1 0
1 1 0 1 1

Output: Number of squares=5 (row 2-from column 1 to column 5)

Example: N=3, M=4

0 0 1 0
1 1 0 0
1 0 1 0

Output: Number of squares=6 (from row 1 to row 3- from column 2 to column 3)

Botje
  • 26,269
  • 3
  • 31
  • 41
Return0
  • 1
  • 3
  • Welcome to Stack Overflow. Please read [the help pages](http://stackoverflow.com/help), take [the SO tour](http://stackoverflow.com/tour), read about [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). Lastly please learn how to create a [mcve]. – Some programmer dude Nov 04 '19 at 11:04
  • pls provide your code and explain your difficulties to solve this problem. we cannot guess, if you have a compile error, questions to an algorithm, what programming language you are using etc.. – Lecagy Nov 04 '19 at 12:06
  • Have you implemented the most obvious solution yet? For every point in the board, try to walk right and down until the "chessboard invariant" no longer holds. – Botje Nov 04 '19 at 12:06
  • A slightly smarter approach would be to generate two N-1 x M-1 grids, where the first has 1 for a cell if the chessboard condition holds on the cell to the right of it, the second grid has 1 for a cell if the chessboard condition holds on the cell below it. At that point you look for the largest rectangle among the following: {rectangle that has 1 in both grids, largest row-section that has 1 in the "right chessboard" grid, largest column-section that has 1 in the "below chessboard" grid} – Botje Nov 04 '19 at 12:11
  • I'm voting to close this question as off-topic because homework questions should show an attempt at solving the problem (see https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions). – TylerH Nov 04 '19 at 16:07

1 Answers1

2
  1. Flip every second cell in a checkerboard pattern
  2. Find the largest rectangle containing only 0s or only 1s.

See Find largest rectangle containing only zeros in an N×N binary matrix for help on the 2nd part.

For your second example:

0 0 1 0
1 1 0 0
1 0 1 0

flipping every 2nd cell produces:

0 1 1 1
0 1 1 0
1 1 1 1

And you can see the rectangle of 1s that you're looking for.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87