基本思路：就是利用一个四维的数组；f[i][j][k][l],就表示为两条路经经过（i,j）和（k,l）的时候做大的和，两个点不能相同，如果相同了的话，就只能有一个值 状态表示： f[i][j][k][l]为 由两条不交叉的线路走到 (i, j)，(k, l) 位置时的最大和 它的上一步可能有四种情况： 第一个点由上走来，第二个点也由上走来，此时的好感度和为f[i - 1][j][k - 1][l] 第一个点由上走来，第二个点则由左走来，此时的好感度和为f[i - 1][j][k][l - 1] 第一个点由左走来，第二个点则由上走来，此时的好感度和为f[i][j - 1][k - 1][l] 第一个点由左走来，第二个点也由左走来，此时的好感度和为f[i][j - 1][k][l - 1] 取四种情况中的最大者加上两个点的权值即可。 特判：一直到终点之前，为了防止路径重叠，不能让两个点相同，所以最后如果两个点相同的话，减去一个点的权值即可。

优化思路：

那么设f[i,j,k]表示走到了第i步，第一条路径向右走了j步，第二条路径向右走了k步。

那么一个NN的矩阵我们从左上角走到右下角需要走2N-2步（不算上起点1,1）

初始化：f[0][1][1]=a[1][1]; step+2=左+右

有一个问题就是现在已知走的步数以及向右走了几步；现在所在点的坐标怎么表示？

比如走了 i 步，此时 向右走了 j 步，此时所在的坐标为（ i+2-j , j ）

f[i,j,k]=max{ f[i-1,j,k] ,f[i-1,j-1,k] ,f[i-1,j-1,k-1], f[i-1,j,k-1] } + (j==k ? a[i+2-j][j] : a[i+2-j][j]+a[i+2-k][k]);

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
long long f[N][N],a[N][N],b[N][N];
int n,m,tmp,num;
int main(){
    cin>>n>>m;
    int x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            tmp=x,num=0;
            while(tmp%2==0)
            {
                num++;tmp/=2;
            } 
            a[i][j]=num;
            tmp=x;num=0;
            while(tmp%5==0)
            {
                num++;tmp/=5;
            }
            b[i][j]=num;
        }
    for(int i=1;i<=n;i++) f[i][1]=a[i][1]+f[i-1][1];
    for(int i=1;i<=m;i++) f[1][i]=a[1][i]+f[1][i-1];
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
            f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
    int ans1=f[n][m];//2的个数
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][1]=b[i][1]+f[i-1][1];
    for(int i=1;i<=m;i++) f[1][i]=b[1][i]+f[1][i-1];
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
            f[i][j]=min(f[i-1][j],f[i][j-1])+b[i][j];
    int ans2=f[n][m];
    //cout<<ans1<<endl<<ans2<<endl;
    cout<<min(ans1,ans2)<<endl;
    return 0;
}