[Python3] DP concise recursive 19 lines, + iterative beats 100%
Starting from any cell[i][j], we go 4 directions top,left, right, down. Go until meeting boundary. Then pick any 2 directions plus cell[i][j] itself to make a \
Starting from any cell[i][j], we go 4 directions top,left, right, down. Go until meeting boundary. Then pick any 2 directions plus cell[i][j] itself to make a \'cornered line\', totally 6 combinations: \'left+cell+top\', \'left+cell+down\', \'left+cell+right\', \'top+cell+right\', \'top+cell+down\', \'right+cell+down\'. Calculating scores for these 6 lines and we will know the highest score that passes cell[i][j]. \nDo the same for all cells and the highest among highest score is the final result. We use 2D prefix sum for 4 directions to achieve O(1) time for each cell.\n\nRecursive: 8274ms beats 50%\n```\n    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n        @functools.lru_cache(None)\n        def factors(num,factor):\n            if num%factor!=0: return 0\n            return 1+factors(num//factor,factor)\n        @functools.lru_cache(None)\n        def dp(i,j,d):\n            if 0<=i<m and 0<=j<n:\n                tmp2,tmp5 = dp(i+d[0],j+d[1],d)\n                return factors(grid[i][j],2)+tmp2,factors(grid[i][j],5)+tmp5\n            return 0,0\n        combo = [[a,b] for a,b in combinations([(-1,0),(0,-1),(1,0),(0,1)],2) if a[0]+b[0]!=0 or a[1]+b[1]!=0]\n        m,n,res=len(grid),len(grid[0]),0\n        for i in range(m):\n            for j in range(n):\n                cur = (factors(grid[i][j],2),factors(grid[i][j],5))\n                for dir1, dir2 in combo:\n                    d1,d2=dp(i,j,dir1),dp(i,j,dir2)\n                    res = max(res,min(d1[0]+d2[0]-cur[0],d1[1]+d2[1]-cur[1]))\n        return res\n```\n\nTo make it even faster\n\t1. We don\'t need to prepare 2D prefix sum for all 4 directions, but only \'up\' and \'left\'. Because \'right\' and \'down\' can be calculated using \'up\' and \'left\'.\n\t2. We don\'t need to go all 6 combinations of 4 directions, but only 4. No need to calculate the 4 \'straight line\' combinations, because for each of them there must exists a \'corner line\' that completely covers it.\n\t3. The function to count factors \'2\' and \'5\' can be cached and put to global to share across test cases\n\nIterative, 4556ms beats 100%\n```\n    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n\t\t@functools.lru_cache(None)\n        def factors(num,factor):\n            if num%factor!=0: return 0\n            return 1+factors(num//factor,factor)\n        m,n=len(grid),len(grid[0])\n        up=[[(0,0) for _ in range(n)]  for _ in range(m)]\n        left=[[(0,0) for _ in range(n)]  for _ in range(m)]\n        for i in range(m):\n            for j in range(n):\n                cur = (factors(grid[i][j],2),factors(grid[i][j],5))\n                grid[i][j] = cur\n                up_prev,left_prev = up[i-1][j], left[i][j-1]\n                up[i][j] = [up_prev[0]+cur[0],up_prev[1]+cur[1]]\n                left[i][j] = [left_prev[0]+cur[0],left_prev[1]+cur[1]]\n        res = 0\n        for i in range(m):\n            for j in range(n):\n                up1,left1,cur = up[i][j], left[i][j], grid[i][j]\n                right1 = [left[i][-1][0]-left1[0]+cur[0],left[i][-1][1]-left1[1]+cur[1]]\n                down1 = [up[-1][j][0]-up1[0]+cur[0],up[-1][j][1]-up1[1]+cur[1]]\n                a = min(left1[0]+up1[0]-cur[0],left1[1]+up1[1]-cur[1])\n                b = min(up1[0]+right1[0]-cur[0],up1[1]+right1[1]-cur[1])\n                c = min(left1[0]+down1[0]-cur[0],left1[1]+down1[1]-cur[1])\n                d = min(right1[0]+down1[0]-cur[0],right1[1]+down1[1]-cur[1])\n                res = max(res,a,b,c,d)\n        return res\n```\n
[]