Computer programming can be a pain sometimes at Xorin's company. There is always the promise that they would finish the project in time, but Xorin knows better than that. That's exactly why, as soon as he is done working long hours during the week, he finds comfort in bizarre activities. This week it shall be… football!
In order to become a real football supporter, Xorin needs to prove his dedication by doing what his great ancestors did back in their day: spray painting a large "U" letter on the wall of some building.
Since Xorin wants to get it over and done with as fast as possible, we need to help him find the maximum possible size for his artwork. The wall is defined as a two-dimensional array with values of 0 - denoting areas of the wall that have already been vandalized - and 1 - denoting areas of the wall that Xorin can paint over.
A valid "U" spray painting is defined by the following sequence:
- Start from some pair of coordinates (i, j) which contains a value of 1.
- Move downwards at least one row.
- Move to the right at least one column.
- Move upwards at least one row.
Note that:
- You can only navigate through cells which contain a value of 1.
- You can at no point navigate outside the borders of the wall.
- The number of rows you move downwards at step 2 does not have to be the same as the number of rows you move upwards at step 4 (that is, the "U" does not have to be symmetric).
The size of a "U" is defined as the number of cells visited during the sequence that generates it.
Input
The first line of input contains integers N and M - the dimensions of the wall.
Each of the following N lines contain M binary values.
Output
You should output a single integer: the maximum size of a valid "U" that Xorin can paint. If there is none, the answer is 0.
Constraints
- 1 ≤ N, M ≤ 500
Samples
| Input | Output | Explanation |
|---|---|---|
| 3 3 101 111 111 | 7 | The largest "U" we can draw has the length 7. It is highlighted in the input. |
| 5 6 100000 110111 000100 110001 110001 | 4 | The only valid "U" is the one in the bottom-left of the wall. |
Let:
- up[i][j] be the length of the longest sequence of 1's that starts at (i, j) and extends upwards.
- left_up[i][j] be the length of the longest sequence of 1's that starts at (i, j), goes to the left 0 or more columns, and then extends upwards 1 or more rows.
When computing left_up[][], make sure that the sequence actually extends upwards, not just to the left. The following testcase fails numerous solutions (answer is 4, not 7):
4 4 1101 1101 0001 1111
The solution is constructed by joining an "L" shape, described by left_up[i][j-1] with a "|", described by up[i][j]. Complexity: O(N * M).
1 #!/usr/bin/python3 2 from copy import deepcopy 3 4 n, m = map(int, input().split()) 5 a = [input() for i in range(n)] 6 up = [[0 for j in range(m)] for i in range(n)] 7 left_up = deepcopy(up) 8 9 for j in range(m): 10 up[0][j] = int(a[0][j]) 11 12 for i in range(1, n): 13 for j in range(m): 14 up[i][j] = up[i-1][j] + 1 if a[i][j] == '1' else 0 15 16 for i in range(n): 17 left_up[i][0] = up[i][0] 18 19 for i in range(n): 20 for j in range(1, m): 21 if a[i][j] == '1': 22 if up[i][j] > 1: 23 left_up[i][j] = up[i][j] 24 25 if left_up[i][j-1] > 1: 26 left_up[i][j] = max(left_up[i][j], 1+left_up[i][j-1]) 27 28 sol = 0 29 for i in range(n): 30 for j in range(1, m): 31 sol = max(sol, left_up[i][j-1] + up[i][j]) 32 33 if sol < 4: 34 sol = 0 35 36 print(sol)
