自分も門松列問題考えてたけど、自分で解答作れずあきらめたのよね…。
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; }
まとめ
自分で考えた門松列問題が解けないのがもどかしい。