tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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);
    }
}