AOJ 1189 A Broken Door

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp）

制約条件

h, w≦30

方針

あるパスの途中におけるコストがaだったとする。
隣の部屋に移動するときのコストは、
max(a, パスの長さ+1, パスの長さ+その移動が失敗したときのコスト)
と表せるので、これでダイクストラすればよい。

区別される状態は、
(位置, 今までに失敗したときの最悪のコスト, パスの長さ)
なので、位置とパスの長さを状態にして、
今までに失敗したときの最悪のコストを最小化するようにすればいい。

パスの長さを状態に入れてなくてだいぶはまった。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
bool tate[32][32], yoko[32][32], v[32][32][900];
int cy[32][32][32][32], ct[32][32][32][32];
int h, w;

void calc(int c[32][32]){
	queue<int> q;
	c[h - 1][w - 1] = 0;
	q.push(h * w - 1);
	while(!q.empty()){
		int y = q.front() / w, x = q.front() % w;
		q.pop();
		rep(d, 4){
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
			if(d % 2 && tate[ny][max(nx, x)] || d % 2 == 0 && yoko[max(ny, y)][nx]) continue;
			if(c[ny][nx] <= c[y][x] + 1) continue;
			c[ny][nx] = c[y][x] + 1;
			q.push(ny * w + nx);
		}
	}
}

int main(){
	while(cin >> h >> w, h){
		memset(tate, 1, sizeof(tate));
		memset(yoko, 1, sizeof(yoko));
		memset(v, 0, sizeof(v));
		
		rep(i, h){
			rep(j, w - 1) cin >> tate[i][j + 1];
			if(i < h - 1) rep(j, w) cin >> yoko[i + 1][j];
		}
		rep(i, h) rep(j, w){
			rep(k, h) rep(l, w) ct[i][j][k][l] = cy[i][j][k][l] = inf;
			if(!tate[i][j]){
				tate[i][j] = 1;
				calc(ct[i][j]);
				tate[i][j] = 0;
			}
			if(!yoko[i][j]){
				yoko[i][j] = 1;
				calc(cy[i][j]);
				yoko[i][j] = 0;
			}
		}
		
		priority_queue<pair<pi, int> > q;
		q.push(mp(mp(0, 0), 0));
		int ans = inf;
		while(!q.empty()){
			int cost = -q.top().first.first, step = -q.top().first.second;
			int y = q.top().second / w, x = q.top().second % w;
			q.pop();
			
			if(v[y][x][step]) continue;
			v[y][x][step] = 1;
			if(y == h - 1 && x == w - 1){
				cout << cost << endl;
				goto END;
			}
			rep(d, 4){
				int ny = y + dy[d], nx = x + dx[d];
				if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
				
				int goal = d % 2 ? ct[ny][max(x, nx)][y][x] : cy[max(ny, y)][nx][y][x];
				if(goal >= inf) continue;
				
				int nc = max(step + 1, max(cost, step + goal));
				if(!v[ny][nx][step + 1] && nc < inf) q.push(mp(mp(-nc, -step - 1), ny * w + nx));
			}
		}
		cout << -1 << endl;
		END:;
	}
	return 0;
}