Given the layout of a rectangular apartment as a grid, with some cells free and some...

Transcribed Image Text:

Given the layout of a rectangular apartment as a grid, with some cells free and some blocked, determine the largest table that can be placed in the apartment, where largest is the largest perimeter of the table. The table must have its edges parallel to the edges of the apartment. You are given nr and nc, the number of rows and columns in the apartment layout, and a 2-dimensional character array showing free squares as " And blocked squares as X. Return the largest possible perimeter for the table. Try to make your code efficient and explain your big-O analysis of your algorithm. ( ive your pseudocode and its bigo analysis. You can use max(nc,nr) as the size of the problem in your bigo.) Example2: 22 The largest perimeter is 8 44 X.XX X.X X. XX The largest perimeter is 10 (a 1x4 table fits in the second column) 33 XX X. XX The largest perimeter is 4 Given the layout of a rectangular apartment as a grid, with some cells free and some blocked, determine the largest table that can be placed in the apartment, where largest is the largest perimeter of the table. The table must have its edges parallel to the edges of the apartment. You are given nr and nc, the number of rows and columns in the apartment layout, and a 2-dimensional character array showing free squares as " And blocked squares as X. Return the largest possible perimeter for the table. Try to make your code efficient and explain your big-O analysis of your algorithm. ( ive your pseudocode and its bigo analysis. You can use max(nc,nr) as the size of the problem in your bigo.) Example2: 22 The largest perimeter is 8 44 X.XX X.X X. XX The largest perimeter is 10 (a 1x4 table fits in the second column) 33 XX X. XX The largest perimeter is 4