ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1171. Lost in Space

Help ! WA on #6 (with three hours debuging , but still can find where it's wrong)
Послано liuyang_elvis 24 окт 2010 19:56
#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;
}