For each test case, in the first line, you should print the maximum sum.
In the next line you should print a string consisting of "L","R","U" and "D", which represents the path you find. If you are in the cell (x,y), "L" means you walk to cell (x,y−1), "R" means you walk to cell (x,y+1), "U" means you walk to cell (x−1,y), "D" means you walk to cell (x+1,y).
In the next line you should print a string consisting of "L","R","U" and "D", which represents the path you find. If you are in the cell (x,y), "L" means you walk to cell (x,y−1), "R" means you walk to cell (x,y+1), "U" means you walk to cell (x−1,y), "D" means you walk to cell (x+1,y).
Sample Input
3 3
2 3 3
3 3 3
3 3 2
Sample Output
25
RRDLLDRR
要求从左上角走到右下角的最大值。
如果n，m中有奇数则可以全部走完。否则需要在（i+j-2）%2 == 1的点中选择一个最小值绕过。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MAXN 300005
#define MIN 0
#define MAX 1000001
int main()
{
int n,m;
ll sum;
char ch;
int x;
//freopen("1007.txt","r",stdin);
while(scanf("%d%d",&n,&m) != EOF)
{
sum = 0;
int minx = 100000;
int mini=-1,minj=-1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
scanf("%d",&x);
sum += x;
if((i+j-2)%2)
{
if(x < minx)
{
minx = x;
mini = i;
minj = j;
}
}
}
if(n % 2 || m % 2)
{
printf("%I64d
",sum);
if(n % 2)
{
for(int k = 1; k <= n; k++)
{
if(k % 2)
ch = 'R';
else
ch = 'L';
for(int i = 1; i <= m-1; i++)
printf("%c",ch);
if(k != n)
printf("D");
}
}
else
{
for(int k = 1; k <= m; k++)
{
if(k % 2)
ch = 'D';
else
ch = 'U';
for(int i = 1; i <= n-1; i++)
printf("%c",ch);
if(k != m)
printf("R");
}
}
}
else
{
printf("%I64d
",sum-minx);
int k=1;
while(1)
{
if(mini%2&&k==mini) break;
if(mini%2==0&&(k+1)==mini) break;
for(int i=2; i<=m; i++)
if(k%2) printf("R");
else printf("L");
printf("D");
k++;
}
if(mini%2)
{
int cx=k;
int cy=1;
while((cy+1)!=minj)
{
printf("DRUR");
cy+=2;
}
printf("DR");
cx++;
cy++;
while(cy!=m)
{
printf("RURD");
cy+=2;
}
k+=2;
}
else
{
int cx=k;
int cy=1;
while(cy!=minj)
{
printf("DRUR");
cy+=2;
}
printf("RD");
cx++;
cy++;
while(cy!=m)
{
printf("RURD");
cy+=2;
}
k+=2;
}
for(int i=k; i<=n; i++)
{
printf("D");
for(int j=2; j<=m; j++)
if(i%2) printf("L");
else printf("R");
}
}
printf("
");
}
return 0;
}