Python, prefix sum solution with explanation
To get a 10 in a path, there must has a 2 and a 5 at least, 2 and 5 are componemts to get more trailing 0s.\n2. the value range of grid is [1, 1000], we can pre
1. To get a 10 in a path, there must has a 2 and a 5 at least, 2 and 5 are componemts to get more trailing 0s.\n2. the value range of grid is [1, 1000], we can precompute how many 2 and 5 are in each number\'s factor.\n3. the path is as longer as good, we just consider 1 coner path only.\n4. we can enumerate each cell as corner, and use prefix sum to get the number of factor in horizontal direction.\n5. enumerate the corner cell from top to bottom or bottom to top to get the number of factor in vertical direction.\n6. if only one row is grid, there is no 1 corner paths, this is a boundary case.\n\ntc is O(1000 + n* m), sc is O(n * m).\n\n```python\n\'\'\'\n1. To form a 10, we need a 5 and a 2.\n2. count how many 5 and 2 the number has for each cell\n3. for each corner path, as longer as good, there are probably trailing zeros\n4. enumerating each cell as corner, one path is top to down, another is left to right\n\n\'\'\'\ncounter_2 = [0] * 1001\ncounter_5 = [0] * 1001\ncounter_2[2] = counter_5[5] = 1\nfor i in range(3, 1001):\n    if i % 2 == 0:\n        counter_2[i] = counter_2[i//2] + 1\n    if i % 5 == 0:\n        counter_5[i] = counter_5[i//5] + 1\nclass Solution:\n    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n        prefix_2 = []\n        prefix_5 = []\n        for row in grid:\n            cur_2 = [0]\n            cur_5 = [0]\n            for x in row:\n                cur_2.append(cur_2[-1] + counter_2[x])\n                cur_5.append(cur_5[-1] + counter_5[x])\n            prefix_2.append(cur_2)\n            prefix_5.append(cur_5)\n        ans = 0\n        row_2_5 = [[0,0] for _ in grid[0]]\n        for i, row in enumerate(grid):\n            for j, x in enumerate(row):\n                c_2_right = prefix_2[i][-1] - prefix_2[i][j]\n                c_5_right = prefix_5[i][-1] - prefix_5[i][j]\n                c_2_left = prefix_2[i][j+1]\n                c_5_left = prefix_5[i][j+1]\n                c_0 = max(min(row_2_5[j][0] + c_2_right, row_2_5[j][1] + c_5_right), min(row_2_5[j][0] + c_2_left, row_2_5[j][1] + c_5_left))\n                ans = max(ans, c_0)\n                row_2_5[j][0] += counter_2[x]\n                row_2_5[j][1] += counter_5[x]\n        \n        row_2_5 = [[0,0] for _ in grid[0]]\n        for i in range(len(grid)-1, -1, -1):\n            for j, x in enumerate(grid[i]):\n                c_2_right = prefix_2[i][-1] - prefix_2[i][j]\n                c_5_right = prefix_5[i][-1] - prefix_5[i][j]\n                c_2_left = prefix_2[i][j+1]\n                c_5_left = prefix_5[i][j+1]\n                c_0 = max(min(row_2_5[j][0] + c_2_right, row_2_5[j][1] + c_5_right), min(row_2_5[j][0] + c_2_left, row_2_5[j][1] + c_5_left))\n                ans = max(ans, c_0)\n                row_2_5[j][0] += counter_2[x]\n                row_2_5[j][1] += counter_5[x]\n        return ans\n```
['Prefix Sum', 'Python']