error in path recovery at a fixed level

My program passed sample But I HAVE WA#1!
My output:
8.6000
4
EDWS

Please give me some hint!

Edited by author 17.05.2007 19:32

Thanks a lot if anyone can give me some help!

The algo is DP + search.
Use DP in different floor.
Use search in the same floor to make sure that no grid will visit twice.

I think my algo is O(n), although the coefficient may be a little large...

It got AC in 0.14sec.
I will continue thinking of this problem to make my pro faster:)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int INF = -(1<<30);

int dp[2][260][4][4],cur,pre;
unsigned int full_path[17][260][4][4];    int full_len[17][260][4][4];

bool can_down[17][4][4];

unsigned int path[17][4][4]; // record the path on each floor use bitset;
int best[17][4][4]; //best[L][i][j] record the largest weighted of the paths from (i,j) whitch has a length of L;
unsigned int sta;    int len, wt;    //length , state and weight;
bool used[4][4];

int N;
int w[17][4][4];
int des_r,des_c;
int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
char opp_dir[4] = {'S', 'N', 'E', 'W'};
int opp_dy[4] = {1, -1, 0 ,0},    opp_dx[4] = {0, 0, 1, -1};
/*
 *      N(0)
 * W(2)      E(3)
 *      S(1)
 * because L less than 15;  so it can be recorded as a 4 bits string which does'n exceed 4^15;
 */

inline bool isok(int r,int c){
    return r >= 0 && r < 4 && c >= 0 && c < 4;
}
void search(int n, int r, int c){

    wt += w[n][r][c];   used[r][c] = true;
    if(best[len][r][c] < wt ){
        best[len][r][c] = wt;
        path[len][r][c] = sta;
    }
    int i;

    //printf("pre_state=%u\n",sta);
    //printf("len = %d\n",len);

    for(i = 0; i < 4; i++){
        int ty = dy[i] + r, tx = dx[i] + c;
        if(isok(ty,tx) && (!used[ty][tx])){
            sta = (sta<<2) + (unsigned int)i;   len ++;
            search(n,ty,tx);
            sta >>= 2;   len --;
        }
    }

    //printf("after_state = %u\n",sta);
    wt -= w[n][r][c];   used[r][c] = false;

}

void print_path(unsigned int p, int len){
    if(len == 0){
        return;
    }
    printf("%c",opp_dir[p%4]);
    print_path(p>>2,len-1);
    des_r += opp_dy[p%4];    des_c += opp_dx[p%4];
}

int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d",&N) != EOF){
        int t,i,j,k;
        for(i = N - 1; i >= 0; i--){
            for(j = 0; j < 4; j++){
                for(k = 0; k < 4; k++){
                    scanf("%d",&w[i][j][k]);
                }
            }

            for(j = 0; j < 4; j++){
                for(k = 0; k < 4; k++){
                    scanf("%d",&t);
                    can_down[i][j][k] = t ? true : false;
                }
            }
        }
        scanf("%d%d",&des_r,&des_c);
        des_r --;   des_c --;

        cur = 0;

        int days;
        for(days = 0; days <= 16; days++){
            if(days == 0){
                fill_n(dp[cur][days][0], 16, 0);
            }else{
                fill_n(dp[cur][days][0], 16, INF);
            }
        }

        fill_n(can_down[0][0], 16, true);
        fill_n(can_down[N][0], 16, false);
        can_down[N][des_r][des_c] = true;

        memset(used, false, sizeof(used));

        for(i = 0; i < N; i++){
            pre = cur;  cur = pre ^ 1;

            for(days = 0; days <= 16 * (i + 1); days++){
                fill_n(dp[cur][days][0], 16, INF);
            }

            for(j = 0; j < 4; j++){
                for(k = 0; k < 4; k++){


                    if(can_down[i][j][k]){
                        for(len = 0; len < 16; len ++){
                            fill_n(best[len][0], 16, INF);
                        }
                        len = 0; sta = 0;   wt = 0;
                        search(i, j, k);
                    }
                    int m, n, pre_days;

                    for(pre_days = i; pre_days <= i*16; pre_days++){
                        if(dp[pre][pre_days][j][k] >=0 ){

                            for(m = 0; m < 4; m++){
                                for(n = 0; n < 4; n++){
                                    if(can_down[i+1][m][n]){

                                        for(int inc_days = 0; inc_days <16; inc_days ++){
                                            days = pre_days + inc_days + 1;
                                            if( best[inc_days][m][n] >= 0 && dp[cur][days][m][n] < dp[pre][pre_days][j][k] + best[inc_days][m][n]){
                                                dp[cur][days][m][n] = dp[pre][pre_days][j][k] + best[inc_days][m][n];
                                                full_path[i][days][m][n] = path[inc_days][m][n];
                                                full_len[i][days][m][n] = inc_days;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

        }

        double res = 0;  int ndays;
        for(days = N; days <= 16*N; days ++){
            double tmp = (dp[cur][days][des_r][des_c]*1.0)/(days*1.0);

            if(tmp > res){
                res = tmp;  ndays = days;
            }
        }

        printf("%.4f\n",res);
        printf("%d\n",ndays-1);

        int flo = N-1;
        if(ndays == 1){
            continue;
        }

        while(true){
            len = full_len[flo][ndays][des_r][des_c]; unsigned int p = full_path[flo][ndays][des_r][des_c];
            //printf("des_r=%d,des_c=%d\n",des_r,des_c);
            print_path(p,len);

            ndays -= len + 1;
            if(ndays <= 1){
                printf("\n");   break;
            }

            printf("D");

            flo --;
        }
    }
    return 0;
}

This is my program.
I'm always  getting WA on test 4. I really don't know why.
If you know, send an E-mail to Sunzheng.david@163.com, or just give a reply.
Thank you very much.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int const dir_x[4] = {0, 1, 0, -1};
int const dir_y[4] = {1, 0, -1, 0};
char const dis_c[4] = {'E', 'S', 'W', 'N'};

typedef long double lld;

bool vis[10][10], found;
int w[20][4][4], max_w[20][4][4][4][4][20], dp[20][300][4][4], link[20][4][4], last[20][300][4][4][4];
char out[500];
int n, size = -1;

void search(int &s_floor, int &s_x, int &s_y, int x, int y, int t){
     vis[x][y] = true;

     for (int i = 0; i < 4; i ++){
         int new_x = x + dir_x[i], new_y = y + dir_y[i];
         if (new_x >= 0 && new_x < 4 && new_y >= 0 && new_y < 4 && !vis[new_x][new_y]){
            int new_w = max_w[s_floor][s_x][s_y][x][y][t] + w[s_floor][new_x][new_y];
            if (new_w > max_w[s_floor][s_x][s_y][new_x][new_y][t + 1]){
               max_w[s_floor][s_x][s_y][new_x][new_y][t + 1] = new_w;
               search(s_floor, s_x, s_y, new_x, new_y, t + 1);
            }
         }
     }

     vis[x][y] = false;
}

void find_way(int &s_floor, int &s_x, int &s_y, int &e_x, int &e_y, int &t_dist, int &t_weight, int x, int y, int dist){
     vis[x][y] = true;
     if (x == e_x && y == e_y && t_weight == max_w[s_floor][s_x][s_y][x][y][dist] && dist == t_dist){
        found = true;
        for (int i = 1; i <= dist / 2; i ++){
            char tmp = out[size + i];
            out[size + i] = out[size + dist - i];
            out[size + dist - i] = tmp;
        }
        size += dist - 1;
     }
     if (found) return;

     for (int i = 0; i < 4; i ++){
         int new_x = x + dir_x[i], new_y = y + dir_y[i];
         if (new_x >= 0 && new_x < 4 && new_y >= 0 && new_y < 4 && !vis[new_x][new_y]){
            int new_w = max_w[s_floor][s_x][s_y][x][y][dist] + w[s_floor][new_x][new_y];
            if (new_w > max_w[s_floor][s_x][s_y][new_x][new_y][dist + 1]){
               max_w[s_floor][s_x][s_y][new_x][new_y][dist + 1] = new_w;
               if (found) return;
               out[size + dist] = dis_c[i];
               find_way(s_floor, s_x, s_y, e_x, e_y, t_dist, t_weight, new_x, new_y, dist + 1);
            }
         }
     }

     vis[x][y] = false;
}

int main(void){
    scanf("%d", &n);
    memset(link, 0, sizeof(link));
    memset(dp, 255, sizeof(dp));
    memset(max_w, 255, sizeof(max_w));

    int s_x, s_y;
    for (int c = 1; c <= n; c ++){
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < 4; i ++){
            for (int j = 0; j < 4; j ++){
                scanf("%d", &w[c][i][j]);
            }
        }

        for (int i = 0; i < 4; i ++){
            for (int j = 0; j < 4; j ++){
                scanf("%d", &link[c][i][j]);
            }
        }

        for (int i = 0; i < 4; i ++){
            for (int j = 0; j < 4; j ++){
                memset(vis, false, sizeof(vis));
                max_w[c][i][j][i][j][1] = w[c][i][j];
                search(c, i, j, i, j, 1);
            }
        }
    }

    scanf("%d%d", &s_x, &s_y);
    s_x --; s_y --;

    dp[0][0][s_x][s_y] = 0;
    link[0][s_x][s_y] = 1;

    for (int c = 1; c <= n; c ++){
        for (int i = 0; i < 4; i ++){
            for (int j = 0; j < 4; j ++){
                for (int k = 0; k <= c * 16; k ++){
                    if (dp[c - 1][k][i][j] >= 0 && link[c - 1][i][j] > 0){
                       for (int l = 0; l < 4; l ++){
                           for (int m = 0; m < 4; m ++){
                               for (int o = 1; o <= 16; o ++){
                                   if (max_w[c][i][j][l][m][o] == -1) continue;
                                   if (dp[c - 1][k][i][j] + max_w[c][i][j][l][m][o] > dp[c][k + o][l][m]){
                                      dp[c][k + o][l][m] = dp[c - 1][k][i][j] + max_w[c][i][j][l][m][o];
                                      last[c][k + o][l][m][0] = i;
                                      last[c][k + o][l][m][1] = j;
                                      last[c][k + o][l][m][2] = o;
                                      last[c][k + o][l][m][3] = max_w[c][i][j][l][m][o];
                                   }
                               }
                           }
                       }
                    }
                }
            }
        }
    }

    lld ans = -1.0;
    int ans_i, ans_j, ans_w;
    for (int i = 0; i < 4; i ++){
        for (int j = 0; j < 4; j ++){
            for (int k = 1; k < n * 16; k ++){
                if (lld(dp[n][k][i][j]) / lld(k) > ans){
                   ans = lld(dp[n][k][i][j]) / lld(k);
                   ans_i = i;
                   ans_j = j;
                   ans_w = k;
                }
            }
        }
    }

    memset(max_w, 255, sizeof(max_w));

    printf("%.4lf\n", double(ans));
    for (int i = n; i >= 1; i --){
        int final_x = last[i][ans_w][ans_i][ans_j][0];
        int final_y = last[i][ans_w][ans_i][ans_j][1];
        int final_w = last[i][ans_w][ans_i][ans_j][2];
        int weight = last[i][ans_w][ans_i][ans_j][3];

        memset(vis, false, sizeof(vis));
        found = false;
        max_w[i][final_x][final_y][final_x][final_y][1] = w[i][final_x][final_y];
        find_way(i, final_x, final_y, ans_i, ans_j, final_w, weight, final_x, final_y, 1);

        ans_i = final_x;
        ans_j = final_y;
        ans_w -= final_w;
        out[++ size] = 'D';
    }

    printf("%d\n", size);
    for (int i = size - 1; i >= 0; i --){
        printf("%c", out[i]);
    }
    printf("\n");
    system("pause");
}

  when n<=15 my program always right but when n=16 than answers a little large than right answer


here is my program

const
  space:array[1..4,1..4]of word=((1,2,4,8),($10,$20,$40,$80),
        ($100,$200,$400,$800),($1000,$2000,$4000,$8000));
var food:array [0..16,1..4,1..4] of byte;
    down:array [0..16,1..4,1..4] of boolean;
    f,been:array [0..16,1..4,1..4,0..256] of word;
    opt,found:array [0..16,1..4,1..4,1..4,1..4,0..16] of word;
    path:array [0..65536] of word;
    d:array [0..16] of string[16];
    n,x,y:byte;
  procedure init;
    var i,j,k,temp:integer;
  begin
    fillchar(food,sizeof(food),0);
    readln(n);
    for i:=n downto 1 do begin
      for j:=1 to 4 do for k:=1 to 4 do read(food[i,j,k]);
      for j:=1 to 4 do for k:=1 to 4 do begin
        read(temp);
        if (temp=1) or (i=1) then down[i,j,k]:=true else down[i,j,k]:=false;
      end;
    end;
    readln(x,y);
  end;
  procedure search(floor,sx,sy,nx,ny,long:byte;get,hash:word);
  begin
    hash:=hash or space[nx,ny];
    if path[hash] and space[nx,ny]>0 then exit;
    path[hash]:=path[hash] or space[nx,ny];
    get:=get+food[floor,nx,ny];
    if (opt[floor,sx,sy,nx,ny,long]=65535) or (get>opt[floor,sx,sy,nx,ny,long]) then begin
      opt[floor,sx,sy,nx,ny,long]:=get;found[floor,sx,sy,nx,ny,long]:=hash;
    end;
    if (nx<4) and (hash and space[nx+1,ny]=0) then search(floor,sx,sy,nx+1,ny,long+1,get,hash);
    if (nx>1) and (hash and space[nx-1,ny]=0) then search(floor,sx,sy,nx-1,ny,long+1,get,hash);
    if (ny<4) and (hash and space[nx,ny+1]=0) then search(floor,sx,sy,nx,ny+1,long+1,get,hash);
    if (ny>1) and (hash and space[nx,ny-1]=0) then search(floor,sx,sy,nx,ny-1,long+1,get,hash);
  end;
  procedure prepar;
    var i,sx,sy,nx,ny,s:integer;
  begin
    fillchar(opt,sizeof(opt),0);fillchar(found,sizeof(found),0);
    for i:=0 to n do for sx:=1 to 4 do for sy:=1 to 4 do for s:=0 to 256 do f[i,sx,sy,s]:=65535;
    for i:=1 to n do
      for sx:=1 to 4 do for sy:=1 to 4 do begin
        fillchar(path,sizeof(path),0);
        for nx:=1 to 4 do for ny:=1 to 4 do for s:=0 to 15 do opt[i,sx,sy,nx,ny,s]:=65535;
        search(i,sx,sy,sx,sy,0,0,0);
      end;
  end;
  procedure solve;
    var i,sx,sy,nx,ny,step,k,s:longint;
  begin
    fillchar(f,sizeof(f),0);fillchar(been,sizeof(been),0);
    for sx:=1 to 4 do for sy:=1 to 4 do for s:=0 to 15 do f[n,sx,sy,s]:=opt[n,x,y,sx,sy,s];
    for i:=n-1 downto 0 do
      for sx:=1 to 4 do for sy:=1 to 4 do if down[i+1,sx,sy] then
        for nx:=1 to 4 do for ny:=1 to 4 do
          for k:=0 to 15 do if opt[i,sx,sy,nx,ny,k]<65535 then
            for step:=1+k to 16*(n-i)+k do begin
              s:=f[i+1,sx,sy,step-k-1]+opt[i,sx,sy,nx,ny,k];
              if (f[i+1,sx,sy,step-k-1]<65535) and ((s>f[i,nx,ny,step]) or (f[i,nx,ny,step]=65535)) then begin
                f[i,nx,ny,step]:=s;
                been[i,nx,ny,step]:=sx*1000+sy*100+k;
              end;
            end;
  end;
  function find(floor,sx,sy,nx,ny,long:byte):string[16];
    var s:word;
  begin
    s:=found[floor,sx,sy,nx,ny,long];
    if (sx=nx) and (sy=ny) and (long=0) then find:=''
    else begin
      if (sx<4) and (s and space[sx+1,sy]>0) then find:='S'+find(floor,sx+1,sy,nx,ny,long-1);
      if (sy<4) and (s and space[sx,sy+1]>0) then find:='E'+find(floor,sx,sy+1,nx,ny,long-1);
      if (sx>1) and (s and space[sx-1,sy]>0) then find:='N'+find(floor,sx-1,sy,nx,ny,long-1);
      if (sy>1) and (s and space[sx,sy-1]>0) then find:='W'+find(floor,sx,sy-1,nx,ny,long-1);
    end;
  end;
  procedure print;
    var  max:real;
         step,ans_step,i,s,c,sx,sy,nx,ny:longint;
  begin
    max:=0;
    for step:=n to 16*n do
      if f[0,1,1,step]/step>max then begin max:=f[0,1,1,step]/step;ans_step:=step;end;
    writeln(max:0:4);
    writeln(ans_step-1);
    step:=ans_step;
    s:=been[0,1,1,step];
    sx:=1;sy:=1;
    c:=s mod 100;s:=s div 100;ny:=s mod 10;nx:=s div 10;
    for i:=0 to n-1 do begin
      if i>0 then d[i]:=find(i,nx,ny,sx,sy,c);
      step:=step-c-1;
      sx:=nx;sy:=ny;
      s:=been[i+1,sx,sy,step];
      c:=s mod 100;s:=s div 100;ny:=s mod 10;nx:=s div 10;
    end;
    d[n]:=find(n,x,y,sx,sy,step);
    for i:=n downto 2 do write(d[i],'D');
    writeln(d[1]);
  end;
begin
  init;
  prepar;
  solve;
  print;
end.

Could you tell me the algorithm?

my email is : smzyjsj1@mail.wh.ah163.net

[deleted by moderator]

Edited by moderator 11.04.2004 01:38

I don't know what to answer as food ratio if l=0?
2
1 20 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
20 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1