kmjp's blog

競技プログラミング参加記です

yukicoder : No.124 門松列(3)

自分も門松列問題考えてたけど、自分で解答作れずあきらめたのよね…。
http://yukicoder.me/problems/222

問題

門松がW*H個の2次元グリッド状に並んでいる。
それぞれの高さはM[i][j]で与えられる。

グリッドで一番左上の位置にある門松から、一番右下にある門松まで、隣接した門松を辿って移動したい。
辿った門松の高さを移動順に並べたものをA[i]とするとき、A[i]が門松列であるような物のうち、移動回数が最小なものを求めよ。

なお、数列が門松列であるとは、任意の連続した3要素の部分列において、3要素がそれぞれ異なっており、かつ2番目に大きな値は3要素の先頭か末尾に来るものを示す。

解法

[現在位置][1つ前にいた位置]を状態として持って、BFSなりダイクストラを行って最小移動回数を求めていけば良い。
[1つ前にいた位置]はW*H通り全要素持つ必要はなく、隣接する4マスのどこから来たかを覚えておくだけ。
(1つ前にいた位置の高さ)(現在位置の高さ)(進もうとする先の高さ)が門松列の条件に合うなら、隣接マスに進んでいく。

int W,H;
ll M[200][200];
int dist[105][105][4];
int dd[4]={1,0,-1,0};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H;
	FOR(y,H) FOR(x,W) cin>>M[y][x];
	
	FOR(y,H) FOR(x,W) FOR(i,4) dist[y][x][i]=100000;
	dist[0][1][0]=1;
	dist[1][0][1]=1;
	queue<int> Q;
	Q.push(0*1000+1*10+0);
	Q.push(1*1000+0*10+1);
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		int cy=k/1000, cx=k/10%100, d=k%10;
		int cy2=cy-dd[d^1],cx2=cx-dd[d];
		FOR(i,4) {
			int ty=cy+dd[i^1];
			int tx=cx+dd[i];
			if(ty<0 || ty>=H || tx<0 || tx>=W) continue;
			if(dist[ty][tx][i]<=dist[cy][cx][d]+1) continue;
			if(M[cy2][cx2]==M[ty][tx]) continue;
			if((M[cy2][cx2]-M[cy][cx])*(M[ty][tx]-M[cy][cx])<=0) continue;
			dist[ty][tx][i]=dist[cy][cx][d]+1;
			Q.push(ty*1000+tx*10+i);
		}
	}
	
	int mi=100000;
	FOR(i,4) mi=min(mi,dist[H-1][W-1][i]);
	if(mi>=100000) mi=-1;
	cout<<mi<<endl;
}

まとめ

自分で考えた門松列問題が解けないのがもどかしい。