|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||12||6||6||50.000%|
After years as a brick-layer, you've been called upon to analyze the instability of brick walls. The instability of a wall can be approximated by the maximum damage to a wall in case of taking one brick out. A brick will fall if all bricks that are directly underneath it are removed. Note that if the space underneath a brick is partially empty, it does not fall. You are given the description of all bricks in a wall, and must determine the instability of the wall as described in the following sections.
There are multiple test cases in the input. Each test case consists of a single line, "M N" (1 ≤ M, N ≤ 100) where M and N indicate the height and width (in units), respectively, of the input wall.
Each of the next M lines is a string of N digits which specifies a row in the wall. Each brick in a row is represented by a substring of the row (like s) such that every digit in s is the same, which is equal to the length of s too. For example, 333 and 22 are two bricks of length 3 and 2 respectively, but 111 specifies three bricks of length one. A 0 in a row means there is no brick in that place of wall. Note that the height of each brick is one. The input terminates with a line containing 0 0. You may assume that the input is correct. This means:
For each test case, write a single line containing maximum sum of the bricks’ lengths that will fall if we take one brick out (including that brick).
4 5 33322 22333 33322 22333 4 6 122333 444422 111111 333333 3 3 022 220 111 0 0
5 8 4