Help ! WA on #6 (with three hours debuging , but still can find where it's wrong)
#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;
}