FastPrep
Problem · Matrix

Maximum Cells

● HardMicrosoftFULLTIMEOA
See Microsoft hiring insights

A map of village is split into a rectangular grid with N rows (numbered from 0 - N - 1) and M columns (numbered from 0 to M - 1). Establish at most two rice cultivation areas in the village, using only cells dedicated to this purpose.

The map is described by an array of strings: the C-th character of the R-th string can be either '.', meaning that the square of land in the R-th row and C-th column is a place where rice cultivation can be established, or '#' if it is an agricultural building.

The shape of the cultivation areas should be a narrow rectangle (vertical with one cell width or horizontal with one cell height).

What is the maximum number of cells that can be used for cultivation by choosing at most two areas?

Given an array of strings A, returns an integer: the maximum number of cells that can be used for cultivation by choosing at most two areas.

Examples
01 · Example 1
A = [".##..", ".#.#.", ".....", "##..#"]
return = 7
Example 1 illustration
02 · Example 2
A = ["#.#", "...", "#.#"]
return = 4
Example 2 illustration
03 · Example 3
A = ["###..", ".....", "###.#"]
return = 7
Example 3 illustration
Constraints
  • N is an integer within the range [1..500]
  • all strings in A are of the same length M within the range [1..500]
  • all strings in A consist only of the characters '.' and/or '#'
    • More Microsoft problems
    drafts saved locally
    public int maximumCells(String[] A) {
  // write your code here
}
    A[".##..", ".#.#.", ".....", "##..#"]
    expected7
    sign in to submit