Mean:
現有一個n*m的迷宮，每一個格子都有一個非負整數，從迷宮的左上角(1,1)到迷宮的右下角(n,m)，并且使得他走過的路徑的整數之和最大，問最大和為多少以及他走的路徑。
analyse:
首先，因為每個格子都是非負整數，而且規定每個格子隻能走一次，是以為了使和盡可能大，必定是走的格子數越多越好。這樣我們就需要考慮一下是不是所有的格子都可以走。
在紙上畫畫，你就會發現，若n、m中至少有一個是奇數的話，必然能夠周遊每一個格子，這樣的話，我們隻需往n、m中為偶數的那個方向先走。
若n、m都為偶數的話，根據棋盤黑白染色(關于棋盤黑白染色問題，想了解的可以點連結)可以得知，當假設(1,1)與(n,m)都為黑色，那麼這條路徑勢必黑色格子數會比白色格子數多1，而棋盤中黑白格子數是相等的，是以棋盤中有一個白格子不會被經過。
或許你自己在研究這道題的時候，會感覺有點混亂，總想着删值最小的格子，但有些格子删了，會有好幾個格子走不到，那是因為删了黑格子的緣故，那樣導緻黑白格子數差2，又要有兩個白格子無法到達，這樣和勢必會比隻删一個白格子要來得小。
是以隻能删白格子
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-18-15.57
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int n,m;
int a[110][110];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
while(~scanf("%d %d",&n,&m))
{
LL sum=0;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
scanf("%d",&a[i][j]),sum+=a[i][j];
}
bool flag=true;
if(n%2==1||m%2==1)
printf("%I64d\n",sum);
if(n%2==1)
{
for(int i=0;i<n-1;++i)
{
for(int j=0;j<m-1;++j)
printf("%c",flag?'R':'L');
printf("%c",'D');
flag=!flag;
}
for(int i=0;i<m-1;++i) printf("%c",flag?'R':'L');
puts("");
continue;
}
if(m%2==1)
for(int i=0;i<m-1;++i)
for(int j=0;j<n-1;++j)
printf("%c",flag?'D':'U');
printf("%c",'R');
for(int i=0;i<n-1;++i) printf("%c",flag?'D':'U');
puts("");
continue;
// structure
int mi=INT_MAX,row,col;
if(((i+j)%2==1) && a[i][j]<mi)
mi=a[i][j],row=i,col=j;
printf("%I64d\n",sum-mi);
flag=true;
if(i<=row-2)
for(int j=0;j<m-1;++j)
printf("%c",flag?'R':'L');
printf("%c",'D'),flag=!flag;
else break;
bool ff=true;
if(flag)
for(int j=0;j<m-1;++j)
if(j!=col)
printf("%c",ff?'D':'U'),ff=!ff;
printf("%c",flag?'R':'L');
else
for(int j=m-1;j>0;--j)
flag=!flag;
if(ff) printf("%c",'D');
for(int i=(row==0)?row+2:row+1;i<n;++i)
printf("D");
flag=!flag;
puts("");
}
return 0;
}