Travelling Salesman Problem
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Special Judge
Problem Description Teacher Mai is in a maze with n rows and m columns. There is a non-negative number in each cell. Teacher Mai wants to walk from the top left corner (1,1) to the bottom right corner (n,m) . He can choose one direction and walk to this adjacent cell. However, he can't go out of the maze, and he can't visit a cell more than once.
Teacher Mai wants to maximize the sum of numbers in his path. And you need to print this path.
Input There are multiple test cases.
For each test case, the first line contains two numbers n,m(1≤n,m≤100,n∗m≥2) .
In following n lines, each line contains m numbers. The j -th number in the i -th line means the number in the cell (i,j) . Every number in the cell is not more than 104 .
Output 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) .
Sample Input
3 3
2 3 3
3 3 3
3 3 2
Sample Output
25
RRDLLDRR
Author xudyh
Source 2015 Multi-University Training Contest 9
題意：現有一個n*m的迷宮(n行m列)，每一個格子都有一個非負整數，Teacher Mai想要從迷宮的左上角(1,1)到迷宮的右下角(n,m)，并且使得他走過的路徑的整數之和最大，問最大和為多少以及他走的路徑。
放上出題人的解題報告
解題思路：首先，因為每個格子都是非負整數，而且規定每個格子隻能走一次，是以為了使和盡可能大，必定是走的格子數越多越好。這樣我們就需要考慮一下是不是所有的格子都可以走。
在紙上畫畫，你就會發現，若n、m中至少有一個是奇數的話，必然能夠周遊每一個格子，這樣的話，我們隻需往n、m中為偶數的那個方向先走就可以了
若n、m都為偶數的話，根據棋盤黑白染色(關于棋盤黑白染色問題，想了解的可以點連結)可以得知，當假設(1,1)與(n,m)都為黑色，那麼這條路徑勢必黑色格子數會比白色格子數多1，而棋盤中黑白格子數是相等的，是以棋盤中有一個白格子不會被經過
或許你自己在研究這道題的時候，會感覺有點混亂，總想着删值最小的格子，但有些格子删了，會有好幾個格子走不到，那是因為删了黑格子的緣故，那樣導緻黑白格子數差2，又要有兩個白格子無法到達，這樣和勢必會比隻删一個白格子要來得小。
是以隻能删白格子
其他的在此不再細講，可以看出題人的解題報告，如果需要我對一些細節進行補充的話，也可以提出來
暫時先放上幾組資料以供參考
3 4
2 3 3 3
3 3 3 3
3 3 3 3
35
RRRDLLLDRRR
4 3
2 3 3
3 3 3
3 3 3
3 3 3
35
DDDRUUURDDD
4 4
3 2 3 3
3 3 3 3
3 3 3 3
3 3 3 3
45
DRRURDDLLLDRRR
4 4
3 3 3 3
3 3 3 3
3 2 3 3
3 3 3 3
45
RRRDLLLDDRRURD
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 105;
const int inf = 1000000000;
const int mod = 1000000007;
int s[N][N];
int main()
{
int n,m,i,j,sum,x,y;
while(~scanf("%d%d",&n,&m))
{
sum=0;x=1,y=2;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
sum+=s[i][j];
if(((i+j)&1)&&s[x][y]>s[i][j])
x=i,y=j;
}
if(n&1||m&1)
{
printf("%d\n",sum);
if(n&1)
{
for(i=1;i<=n;i++)
{
for(j=1;j<m;j++)
if(i&1)
printf("R");
else
printf("L");
if(i<n)
printf("D");
else
puts("");
}
}
else
{
for(i=1;i<=m;i++)
{
for(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-s[x][y]);
for(i=1;i<=n;i+=2)
{
if(x==i||x==i+1)
{
for(j=1;j<y;j++)
{
if(j&1)
printf("D");
else
printf("U");
printf("R");
}
if(y<m)
printf("R");
for(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(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");
}
}
puts("");
}
}
return 0;
}
菜鳥成長記