Problem's Link:

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'); 
flag
=!
flag; 
}
}
for( 
int
i
=
0; 
i
<n 
-
1; 
++
i) 
printf( 
"%c"
,
flag
?
'D'
:
'U'); 
puts( 
""); 
continue; 
}
// structure
int
mi
=
INT_MAX
,
row
,
col; 
for( 
int
i
=
0; 
i
<n; 
++
i) 
{ 
for( 
int
j
=
0; 
j
<
m; 
++
j) 
{ 
if((( 
i
+
j) 
%
2
==
1) 
&&
a
[
i
][
j
]
<
mi) 
mi
=
a
[
i
][
j
],
row
=
i
,
col
=
j; 
}
}
printf( 
"%I64d
\n
"
,
sum
-
mi); 
flag
=
true; 
for( 
int
i
=
0; 
i
<n; 
++
i) 
{ 
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) 
{ 
if( 
j
!=
col) 
printf( 
"%c"
,
ff
?
'D'
:
'U'
),
ff
=!
ff; 
printf( 
"%c"
,
flag
?
'R'
:
'L'); 
}
}
flag
=!
flag; 
if( 
ff) 
printf( 
"%c"
,
'D'); 
for( 
int
i
=( 
row
==
0) 
?
row
+
2
:
row
+
1; 
i
<n; 
++
i) 
{ 
printf( 
"D"); 
for( 
int
j
=
0; 
j
<
m
-
1; 
++
j) 
printf( 
"%c"
,
flag
?
'R'
:
'L'); 
flag
=!
flag; 
}
puts( 
""); 
}
return
0; 
}
/*
*/

转载地址：http://nkdpa.baihongyu.com/

你可能感兴趣的文章

service password-encryption，enable secret，enable password区别