409981: GYM103886 H Bombs and Balloons

Envy and Batrick have stolen some of Ary's prized cereal!

Unfortunately, Ary has an obstacle for your escape: a $$$n$$$ x $$$m$$$ grid, where each cell is either a balloon or a bomb.

Envy and Batrick walk across the grid one row at a time holding a barbed wire between them (that can pop balloons and also activate bombs).

First, Envy and Batrick starts at position $$$i$$$ and $$$j$$$ $$$(1 \le i, j \le m)$$$ and approach the first row of the grid, popping all balloons in the range $$$[min(i, j), max(i, j)]$$$ within that first row. Note that Envy can be on the left or on the right of Batrick.

Then, they repeat the following process until exiting the grid out the bottom row: Envy or Batrick (at most one of them) may change their horizontal position (move to some $$$1 \le k \le M$$$) before approaching the next row of the grid and again popping all balloons and activating bombs in the inclusive range between them.

What is the maximum number of balloons Bessie and Elsie can pop without activating any bombs?

The first line contains $$$2$$$ integers, $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^3)$$$

Next $$$n$$$ lines contain $$$m$$$ characters describing the board (where '#' is a bomb and '.' is a balloon).

Output one integer, the maximum number of balloons that they can pop in the grid without activating any bombs, or -1 if they are guaranteed to turn on at least one bomb.

3 5
.....
...#.
#....

11

5 5
.....
.##.#
####.
.####
.....

-1

5 5
.....
...#.
.....
.....
.....

23

For the first sample, Envy and Batrick can start at horizontal positions $$$i = 1$$$ and $$$j = 5$$$, popping $$$5$$$ balloons in the first row of the grid.

Then, Batrick can move to position $$$j = 2$$$, so that they pop $$$2$$$ balloons in the second row of the grid.

Finally, Envy can move to position $$$i = 5$$$, so that Envy and Batrick pop $$$4$$$ balloons in the last row of the grid, for a total of $$$5 + 2 + 4 = 11$$$ balloons popped.

It can be shown that this is the maximum amount of balloons they can pop.

Problem Credits: Ariel Shehter