题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5402

题意：现有一个n*m的迷宫(n行m列)，每一个格子都有一个非负整数，Teacher Mai想要从迷宫的左上角(1,1)到迷宫的右下角(n,m)，并且使得他走过的路径的整数之和最大，问最大和为多少以及他走的路径。

解法：

为什么要这么做？看论文：点击打开链接 这是棋盘染色的论文

知道这个结论之后，随便画一画就知道怎么构造了。


#include <bits/stdc++.h>
using namespace std;
int n,m,sum,x,y,a[102][102];

int main()
{
    while(~scanf("%d %d", &n,&m))
    {
        sum = 0;
        x = 1, y = 2;
        for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            scanf("%d", &a[i][j]);
            sum += a[i][j];
            if((i+j)&1&&a[x][y]>a[i][j]){
                x=i;
                y=j;
            }
        }
        if(n&1||m&1){
            printf("%d\n", sum);
            if(n&1){
                for(int i=1; i<=n; i++){
                    for(int j=1; j<m; j++){
                        if(i&1) printf("R");
                        else printf("L");
                    }
                    if(i<n) printf("D");
                    else puts("");
                }
            }
            else{
                for(int i=1; i<=m; i++){
                    for(int j=1; j<n; j++){
                        if(i&1) printf("D");
                        else printf("U");
                    }
                    if(i<m) printf("R");
                    else puts("");
                }
            }
        }
        else{
            printf("%d\n", sum-a[x][y]);
            for(int i=1; i<=n; i+=2){
                if(x==i||x==i+1){
                    for(int j=1; j<y; j++){
                        if(j&1) printf("D");
                        else printf("U");
                        printf("R");
                    }
                    if(y<m) printf("R");
                    for(int j=y+1; j<=m; j++){
                        if(j&1) printf("U");
                        else printf("D");
                        if(j<m) printf("R");
                    }
                    if(i<n-1) printf("D");
                }
                else if(x<i){
                    for(int j=1; j<m; j++){
                        printf("L");
                    }
                    printf("D");
                    for(int j=1; j<m; j++){
                        printf("R");
                    }
                    if(i<n-1) printf("D");
                }
                else{
                    for(int j=1; j<m; j++){
                        printf("R");
                    }
                    printf("D");
                    for(int j=1; j<m; j++){
                        printf("L");
                    }
                    if(i<n-1) printf("D");
                }
            }
            puts("");
        }
    }
    return 0;
}