Maximum-Cup 2013 : G - King's Ring Tower

長らく解いていなかったのでチャレンジ。
実装は手間がかかるけど、難易度自体は高くないな…。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_g

問題

問題文は長いので上記URLを参照。
10x10x10のフィールドを開始位置からゴール位置に至るコストを答える問題。
１マスの移動にコストが１かかるほか、敵がいるマスは敵のレベル分コストが増加する。
また、自分より高いレベルの敵がいるマスは通過できず、同レベルの敵のマスを通過するとレベルが１上がる。

解法

３次元分の座標と、自分のレベルを状態としてダイクストラ法で解いていくだけ。
問題文にちょこちょこ罠があって、開始位置より下のフロアに降りれないとかこそっと書いてあるので注意。

int T,W,H,L;
char fl[100];
int field[12][12][12];
int SX,SY,SZ,GX,GY,GZ;
int SDX[12],SDY[12],SUX[12],SUY[12];
ll cost[12][12][12][101];
ll dcost[101];

void solve() {
	int f,i,j,k,l,x,y,z;
	cin>>T>>W>>H>>L;
	L=min(L,100);
	
	gets(fl); /* skip first line*/
	FOR(z,T) {
		FOR(y,H) {
			gets(fl);
			FOR(x,W) {
				if(fl[x*2]=='K') SX=x, SY=y,SZ=z;
				if(fl[x*2]=='$') GX=x, GY=y, GZ=z;
				if(fl[x*2]=='-') SDX[z]=x, SDY[z]=y;
				if(fl[x*2]=='_') SUX[z]=x, SUY[z]=y;
				if(fl[x*2]==' ' || fl[x*2]=='#') field[z][y][x]=1000;
				if(fl[x*2]>='0' && fl[x*2]<='9') field[z][y][x]=(fl[x*2]-'0')*10+fl[x*2+1]-'0';
				if(fl[x*2]=='H') field[z][y][x]=100;
				FOR(j,101) cost[z][y][x][j]=1LL<<40;
			}
		}
	}
	cost[SZ][SY][SX][L]=0;
	
	set<pair<ll,int> > S;
	S.insert(make_pair(0,L*1000+SZ*100+SY*10+SX));
	
	while(!S.empty()) {
		pair<ll,int> key = *S.begin();
		S.erase(S.begin());
		ll co=key.first;
		int cz=(key.second/100)%10,cy=(key.second/10)%10,cx=key.second%10;
		j=key.second/1000;
		//_P("%d %d %d %d %lld\n",cz,cy,cx,j,co);
		FOR(f,4) {
			int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
			int ty=cy+dy[f],tx=cx+dx[f];
			if(ty<0 || ty>=H || tx<0 || tx>=W) continue;
			if(field[cz][ty][tx]>j) continue;
			if(field[cz][ty][tx]==j && j<=99) {
				// same level emeny
				if(cost[cz][ty][tx][j+1] > co+j+1) {
					if(cost[cz][ty][tx][j+1]<1LL<<40) S.erase(make_pair(cost[cz][ty][tx][j+1],(j+1)*1000+cz*100+ty*10+tx));
					cost[cz][ty][tx][j+1] = co+j+1;
					S.insert(make_pair(cost[cz][ty][tx][j+1],(j+1)*1000+cz*100+ty*10+tx));
				}
			}
			else if(cost[cz][ty][tx][j] > co+field[cz][ty][tx]+1) {
				if(cost[cz][ty][tx][j]<1LL<<40) S.erase(make_pair(cost[cz][ty][tx][j],j*1000+cz*100+ty*10+tx));
				cost[cz][ty][tx][j] = co+field[cz][ty][tx]+1;
				S.insert(make_pair(cost[cz][ty][tx][j],j*1000+cz*100+ty*10+tx));
				
				// downstair
				if(ty==SDY[cz] && tx==SDX[cz] && cz>SZ && cost[cz-1][SUY[cz-1]][SUX[cz-1]][j]>cost[cz][ty][tx][j]+1) {
					if(cost[cz-1][SUY[cz-1]][SUX[cz-1]][j]<1LL<<40)
						S.erase(make_pair(cost[cz-1][SUY[cz-1]][SUX[cz-1]][j],j*1000+(cz-1)*100+SUY[cz-1]*10+SUX[cz-1]));
					cost[cz-1][SUY[cz-1]][SUX[cz-1]][j] = cost[cz][ty][tx][j]+1;
					S.insert(make_pair(cost[cz-1][SUY[cz-1]][SUX[cz-1]][j],j*1000+(cz-1)*100+SUY[cz-1]*10+SUX[cz-1]));
				}
				// upstair
				if(ty==SUY[cz] && tx==SUX[cz] && cost[cz+1][SDY[cz+1]][SDX[cz+1]][j]>cost[cz][ty][tx][j]+1) {
					if(cost[cz+1][SDY[cz+1]][SDX[cz+1]][j]<1LL<<40)
						S.erase(make_pair(cost[cz+1][SDY[cz+1]][SDX[cz+1]][j],j*1000+(cz+1)*100+SDY[cz+1]*10+SDX[cz+1]));
					cost[cz+1][SDY[cz+1]][SDX[cz+1]][j] = cost[cz][ty][tx][j]+1;
					S.insert(make_pair(cost[cz+1][SDY[cz+1]][SDX[cz+1]][j],j*1000+(cz+1)*100+SDY[cz+1]*10+SDX[cz+1]));
				}
			}
		}
	}
	
	ll mi=1LL<<40;
	FOR(j,101) mi=min(mi,cost[GZ][GY][GX][j]);
	if(mi>=1LL<<40) cout << "Impossible" << endl;
	else cout << mi << endl;
}

まとめ

最初、常に下に降りれないと思ってフロア毎にダイクストラしたらWAだった。
初期のフロアよりは下に降りれないのね。