simple dynamic programming (dp) O(n*m)
\nclass Solution {\npublic:\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        int n=grid.size(),m=grid[0].size();\n        int ans=0;\n        int
```\nclass Solution {\npublic:\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        int n=grid.size(),m=grid[0].size();\n        int ans=0;\n        int dp1[2][n+2][m+2],dp2[2][n+2][m+2],dp3[2][n+2][m+2],dp4[2][n+2][m+2];\n        memset(dp1,0,sizeof dp1);\n        memset(dp2,0,sizeof dp2);\n        memset(dp3,0,sizeof dp3);\n        memset(dp4,0,sizeof dp4);\n\n        for(int x=0;x<grid.size();x++){\n            for(int z=0;z<grid[0].size();z++){\n                int cnt2=0,cnt5=0;\n                int num=grid[x][z];\n                while(num%2==0)num/=2,cnt2++;\n                while(num%5==0)num/=5,cnt5++;\n                dp1[0][x+1][z+1]=dp2[0][x+1][z+1]=dp3[0][x+1][z+1]=dp4[0][x+1][z+1]=cnt2;\n                dp1[1][x+1][z+1]=dp2[1][x+1][z+1]=dp3[1][x+1][z+1]=dp4[1][x+1][z+1]=cnt5;\n            }\n        }\n        for(int i=1;i<=n;i++){//up to down\n            for(int j=1;j<=m;j++){\n                dp1[0][i][j]+=dp1[0][i-1][j];\n                dp1[1][i][j]+=dp1[1][i-1][j];\n                // std::cout<<dp1[0][i][j]<<","<<dp1[1][i][j]<<" ";\n            }//std::cout<<"\\n";\n        }\n        // std::cout<<"\\n";\n        for(int i=n;i>=1;i--){//down to up\n            for(int j=1;j<=m;j++){\n                dp2[0][i][j]+=dp2[0][i+1][j];\n                dp2[1][i][j]+=dp2[1][i+1][j];\n                // std::cout<<dp2[0][i][j]<<","<<dp2[1][i][j]<<" ";\n            }//std::cout<<"\\n";\n        }\n        // std::cout<<"\\n";\n        for(int i=1;i<=n;i++){//left to right\n            for(int j=1;j<=m;j++){\n                dp3[0][i][j]+=dp3[0][i][j-1];\n                dp3[1][i][j]+=dp3[1][i][j-1];\n                // std::cout<<dp3[0][i][j]<<","<<dp3[1][i][j]<<" ";\n            }//std::cout<<"\\n";\n        }\n        // std::cout<<"\\n";\n        for(int i=1;i<=n;i++){//right to left\n            for(int j=m;j>=1;j--){\n                dp4[0][i][j]+=dp4[0][i][j+1];\n                dp4[1][i][j]+=dp4[1][i][j+1];\n               //std::cout<<dp4[0][i][j]<<","<<dp4[1][i][j]<<" ";\n            }//std::cout<<"\\n";\n        }\n        //std::cout<<"\\n";\n        for(int i=1;i<=n;i++){//solve\n            for(int j=1;j<=m;j++){\n            \n                    ans=max(ans,min(dp4[0][i][j+1]+dp2[0][i][j],dp4[1][i][j+1]+dp2[1][i][j]));\n                    ans=max(ans,min(dp3[0][i][j-1]+dp1[0][i][j],dp3[1][i][j-1]+dp1[1][i][j]));\n                    ans=max(ans,min(dp3[0][i][j-1]+dp2[0][i][j],dp3[1][i][j-1]+dp2[1][i][j]));\n                    ans=max(ans,min(dp4[0][i][j+1]+dp1[0][i][j],dp4[1][i][j+1]+dp1[1][i][j]));\n                \n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Prefix Sum']