搜集糖果

 搜集糖果(candy)

【题目描述】

在一片N*M的四连通(一个点与它上方、下方、左方、右方这四个点连通)田野中，散布着很多很多的糖果。Ryz现在要以(x,y)为起点去搜集糖果。Ryz搜集当前点的糖果并走到下一格需要一个单位时间。由于田野中还有许多其它的喜欢吃糖果的小动物，所以每过一个单位时间，所有格子上的糖果都会减少一半。Ryz不喜欢做徒劳的工作，所有同一个格子不能走两遍。如果当前点周围所有连通的格子都已经被走过了，那么这次搜集就结束了。现在请你帮助他收集尽量多的糖果，输出你的移动序列，用”U”代表向上，”D”代表向下，”R”代表向右，”L”代表向左。

【输入格式】

         第一行两个正整数N,M,x,y，表示地图大小和初始位置。

         接下来的N行M列描述了每个格子的初始糖果s[i][j]。

【输出格式】

         一行若干个字符，表示你的移动序列。

【输入样例1】

2 2 1 1

1 16

8 4

【输出样例1】

RDL

【输入样例2】

3 3 1 1

6 9 4

7 1 3

8 2 5

【输出样例2】

RRDDLLUR

【数据范围与约定】

对于100%的数据,n<=100,m<=100,0<=s[i][j]<=100000

对于100%的数据,s[i][j]互不相等。

下表列出了各个数据点n,m的范围。

 题解：这是一道很玄学的搜索题，主要思想就是：我们先向前走N步（N要适当，大了会超时，小了会WA），然后选择最优的一条路走，直至走完。能否AC各凭天运吧。

Code：

{$M 20000000,0,maxlongint}
var
  n,m,x,y,i,j,ans:longint;
  t:array[0..18]of int64;
  dx,dy:array[1..4]of longint;
  dd:array[1..4]of char;
  s:array[0..101,0..101]of longint;
  flag:array[0..101,0..101]of boolean;
procedure dfs1(x,y,z:longint;num:int64);
var i,nx,ny:longint;
begin
  if num>ans then ans:=num;
  if z>=13 then exit;
  for i:=1 to 4 do
  begin
    nx:=x+dx[i];
    ny:=y+dy[i];
    if (nx<1)or(ny<1)or(nx>n)or(ny>m)or flag[nx,ny] then continue;
    flag[nx,ny]:=true;
    dfs1(nx,ny,z+1,num+t[13-z-1]*s[nx,ny]);
    flag[nx,ny]:=false;
  end;
end;
procedure dfs2(x,y:longint);
var i,nx,ny,sx,sy,si,max:longint;
begin
  max:=-1<<29;
  for i:=1 to 4 do
  begin
    nx:=x+dx[i];ny:=y+dy[i];
    if (nx<1)or(ny<1)or(nx>n)or(ny>m)or flag[nx,ny] then continue;
    flag[nx,ny]:=true;
    ans:=0;
    dfs1(nx,ny,0,t[13]*s[nx,ny]);
    flag[nx,ny]:=false;
    if ans>max then
    begin
      max:=ans;sx:=nx;sy:=ny;si:=i;
    end;
  end;
  if max=-1<<29 then exit;
  write(dd[si]);
  flag[sx,sy]:=true;
  dfs2(sx,sy);
end;
begin
  assign(input,'candy.in');reset(input);
  assign(output,'candy.out');rewrite(output);
  dx[1]:=-1;dy[1]:=0;dd[1]:='U';
  dx[2]:=0;dy[2]:=-1;dd[2]:='L';
  dx[3]:=0;dy[3]:=1;dd[3]:='R';
  dx[4]:=1;dy[4]:=0;dd[4]:='D';
  readln(n,m,x,y);
  t[0]:=1;
  for i:=1 to 17 do t[i]:=t[i-1]*2;
  for i:=1 to n do
    for j:=1 to m do read(s[i,j]);
  flag[x,y]:=true;
  dfs2(x,y);writeln;
  close(input);close(output);
end.