AOJ 0234: Aizu Buried Treasure
ブログに記事を書きます Advent Calendar 2014 - Adventar
試験がやばくて時間がないからこれで許して。
#include<stdio.h> #include<algorithm> #include<queue> using namespace std; int dp[12][12][12][12][52]; int v[12][12][12][12][52]; int t[12][12]; struct wolf{ int cost; int row; int col; int L; int R; int v; wolf(){} wolf(int a,int b,int c,int d,int e,int f){ cost=a;row=b;col=c;L=d;R=e;v=f; } }; inline bool operator<(const wolf&a,const wolf&b){ if(a.cost!=b.cost)return a.cost>b.cost; return false; } int main(){ int a,b; while(scanf("%d%d",&b,&a),a){ int c,d,e;scanf("%d%d%d",&c,&d,&e); for(int i=0;i<a;i++)for(int j=0;j<b;j++)scanf("%d",&t[i][j]); for(int i=0;i<a;i++)for(int j=0;j<b;j++) for(int k=0;k<b;k++)for(int l=0;l<b;l++) for(int m=0;m<=d;m++) dp[i][j][k][l][m]=999999999; for(int i=0;i<a;i++)for(int j=0;j<b;j++)for(int k=0;k<b;k++) for(int l=0;l<b;l++)for(int m=0;m<=d;m++) v[i][j][k][l][m]=0; priority_queue<wolf>Q; if(e<=1){ printf("NA\n");continue; } for(int i=0;i<b;i++){ if(t[0][i]>0){ dp[0][i][i][i][min(d,e-1+t[0][i])]=0; Q.push(wolf(0,0,i,i,i,min(d,e-1+t[0][i]))); }else{ dp[0][i][i][i][e-1]=-t[0][i]; Q.push(wolf(-t[0][i],0,i,i,i,e-1)); } } while(Q.size()){ wolf at=Q.top(); Q.pop(); if(v[at.row][at.col][at.L][at.R][at.v])continue; v[at.row][at.col][at.L][at.R][at.v]=1; if(at.v==1)continue; if(at.col){ if(at.col==at.L){ if(t[at.row][at.col-1]>0){ int tov=min(d,at.v-1+t[at.row][at.col-1]); if(!v[at.row][at.col-1][at.col-1][at.R][tov]&&dp[at.row][at.col-1][at.col-1][at.R][tov]>at.cost){ dp[at.row][at.col-1][at.col-1][at.R][tov]=at.cost; Q.push(wolf(at.cost,at.row,at.col-1,at.col-1,at.R,tov)); } }else{ if(!v[at.row][at.col-1][at.col-1][at.R][at.v-1]&&dp[at.row][at.col-1][at.col-1][at.R][at.v-1]>at.cost-t[at.row][at.col-1]){ dp[at.row][at.col-1][at.col-1][at.R][at.v-1]=at.cost-t[at.row][at.col-1]; Q.push(wolf(at.cost-t[at.row][at.col-1],at.row,at.col-1,at.col-1,at.R,at.v-1)); } } }else{ if(!v[at.row][at.col-1][at.L][at.R][at.v-1]&&dp[at.row][at.col-1][at.L][at.R][at.v-1]>at.cost){ dp[at.row][at.col-1][at.L][at.R][at.v-1]=at.cost; Q.push(wolf(at.cost,at.row,at.col-1,at.L,at.R,at.v-1)); } } } if(at.col<b-1){ if(at.col==at.R){ if(t[at.row][at.col+1]>0){ int tov=min(d,at.v-1+t[at.row][at.col+1]); if(!v[at.row][at.col+1][at.L][at.col+1][tov]&&dp[at.row][at.col+1][at.L][at.col+1][tov]>at.cost){ dp[at.row][at.col+1][at.L][at.col+1][tov]=at.cost; Q.push(wolf(at.cost,at.row,at.col+1,at.L,at.col+1,tov)); } }else{ if(!v[at.row][at.col+1][at.L][at.col+1][at.v-1]&&dp[at.row][at.col+1][at.L][at.col+1][at.v-1]>at.cost-t[at.row][at.col+1]){ dp[at.row][at.col+1][at.L][at.col+1][at.v-1]=at.cost-t[at.row][at.col+1]; Q.push(wolf(at.cost-t[at.row][at.col+1],at.row,at.col+1,at.L,at.col+1,at.v-1)); } } }else{ if(!v[at.row][at.col+1][at.L][at.R][at.v-1]&&dp[at.row][at.col+1][at.L][at.R][at.v-1]>at.cost){ dp[at.row][at.col+1][at.L][at.R][at.v-1]=at.cost; Q.push(wolf(at.cost,at.row,at.col+1,at.L,at.R,at.v-1)); } } } if(at.row<a-1){ if(t[at.row+1][at.col]>0){ int tov=min(d,at.v-1+t[at.row+1][at.col]); if(!v[at.row+1][at.col][at.col][at.col][tov]&&dp[at.row+1][at.col][at.col][at.col][tov]>at.cost){ dp[at.row+1][at.col][at.col][at.col][tov]=at.cost; Q.push(wolf(at.cost,at.row+1,at.col,at.col,at.col,tov)); } }else{ if(!v[at.row+1][at.col][at.col][at.col][at.v-1]&&dp[at.row+1][at.col][at.col][at.col][at.v-1]>at.cost-t[at.row+1][at.col]){ dp[at.row+1][at.col][at.col][at.col][at.v-1]=at.cost-t[at.row+1][at.col]; Q.push(wolf(at.cost-t[at.row+1][at.col],at.row+1,at.col,at.col,at.col,at.v-1)); } } } } int ret=999999999; for(int i=0;i<b;i++){ for(int j=0;j<b;j++)for(int k=0;k<b;k++) for(int l=1;l<=d;l++)ret=min(ret,dp[a-1][i][j][k][l]); } if(ret>c){ printf("NA\n"); }else printf("%d\n",ret); } }
