题意：

给你一个矩阵，每个值都是非负，然后让你从左上角走到右下角，每个点只能走一次，求到终点的最大值，还要输出一条路径

思路：

一开始拿到还以为搜索之类的，但是发现神特么暴力+麻烦（因为路径这个东西。。。），虽然路径现在也是能写，但是开个数组。。。还是嫌麻烦。题意给出的非负的，而且如果矩阵的行或列是奇数的时候就一定能走完，具体走法，还是具体实现就好了。但是偶行偶列不行，后来想了一个是不是全部值-一个最小。。。随便举个反例就会知道，这个存在最小的绕不过去，还得搭上旁边的几个，所以才有了正确的解法，我们先去找那些能绕过去的位置，也就是饶过他，我可以通过其他的点走到右下角。

然后就是这样。。。。

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

0表示可以绕过去，也就是除了他我可以走完。

那么就在能绕过去那边找一个最小的，为什么这样就是对的呢，如果我绕过的是不能除了他就走完的位置的话，那势必会减少至少一个旁边的位置，所以我去找最小可以绕过的位置，然后饶过他，就是正确的方法。

然后我们只要去判断这个最小在哪一行就好了，最好就是两行，因为从起点出去，那个点在0位置的话，我们可以选定两行发现是一定满足从左上进，右下出，那么在这个两行前面的行我们就是右 下 左 再下，两行下面的行就是左 下 右 ，看情况再下，就是这样。。。

说的不好，但是代码还是很清楚的。。。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int INF=1e4+10;

const int N=1e2+10;

int ma[N][N];

int main()

{

    int n,m,sum;

    int tmin;

    int i,j;

    int x,y;

    while(~scanf("%d%d",&n,&m))

    {

        tmin=INF;

        sum=0;

        for(i=1; i<=n; i++)

        {

            for(j=1; j<=m; j++)

            {

                scanf("%d",&ma[i][j]);

                sum+=ma[i][j];

                if(m%2==0 && n%2==0)

                {

                    if(i%2==0 && j%2!=0)

                    {

                        if(ma[i][j]<tmin)

                        {

                            tmin=ma[i][j];

                            x=i;

                            y=j;

                        }

                    }

                    if(i%2!=0 && j%2==0)

                    {

                        if(ma[i][j]<tmin)

                        {

                            tmin=ma[i][j];

                            x=i;

                            y=j;

                        }

                    }

                }

            }

        }

        if(n%2!=0)

        {

            printf("%d\n",sum);

            for(i=1; i<=n; i++)

            {

                if(i%2!=0)

                {

                    for(j=1; j<=m-1; j++)

                        printf("R");

                }

                if(i%2==0)

                {

                    for(j=1; j<=m-1; j++)

                        printf("L");

                }

                if(i==n && j==m)

                    break;

                else

                    printf("D");

            }

        }

        else if(m%2!=0)

        {

            printf("%d\n",sum);

            for(i=1; i<=m; i++)

            {

                if(i%2!=0)

                {

                    for(j=1; j<=n-1; j++)

                        printf("D");

                }

                if(i%2==0)

                {

                    for(j=1; j<=n-1; j++)

                        printf("U");

                }

                if(i==m && j==n)

                    break;

                else

                    printf("R");

            }

        }

        else

        {

            printf("%d\n",sum-tmin);

            for(i=1; i<=n; i+=2)

            {

                if(x==i || x==i+1)

                {

                    //上下

                    for(j=1; j<y; j++)

                    {

                        if(j%2!=0)

                            printf("D");

                        else

                            printf("U");

                        printf("R");

                    }

                    if(y<m)

                        printf("R");

                    //上下

                    for(j=y+1; j<=m; j++)

                    {

                        if(j%2!=0)

                            printf("U");

                        else

                            printf("D");

                        if(j<m)

                            printf("R");

                    }

                    if(i<n-1)

                        printf("D");

                }

                else if(x<i)//左下右

                {

                    for(j=1; j<m; j++)

                        printf("L");

                    printf("D");

                    for(j=1; j<m; j++)

                        printf("R");

                    if(i<n-1)

                        printf("D");

                }

                else//右下左

                {

                    for(j=1; j<m; j++)

                        printf("R");

                    printf("D");

                    for(j=1; j<m; j++)

                        printf("L");

                    printf("D");

                }

            }

        }

        printf("\n");

    }

    return 0;

}

/*

4 4

5 5 5 5

1 5 5 5

5 5 5 5

5 5 5 5

4 4

5 1 5 5

5 5 5 5

5 5 5 5

5 5 5 5

*/