yukicoder : No.367 ナイトの転身

365でLISを書いてしまいタイムロス。★1でLISはないなと思ったのにまんまとやってしまった。
http://yukicoder.me/problems/996

問題

２次元グリッドが与えられるので、その上でチェスの駒をスタート地点からゴール地点に移動させたい。
初期状態では駒はナイトのように動くことができる。

一部のグリッドは赤く塗られており、移動の際それらの上に止まると、以後の駒の移動先がナイトとミニビショップ（斜め１マスのみ移動可能）で切り替わる。
最適な移動経路を取るとき、最短何手でゴール地点に移動できるか。

解法

現在位置と現在の移動手段を状態としてBFSしていく。

int H,W;
string S[1010];

int dist[501][501][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int sx,sy,gy,gx;
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) {
		dist[y][x][0]=dist[y][x][1]=1<<20;
		if(S[y][x]=='S') sy=y,sx=x;
		if(S[y][x]=='G') gy=y,gx=x;
	}
	
	vector<pair<int,int>> V[2];
	V[0] = {{1,2},{2,1},{1,-2},{2,-1},{-1,2},{-2,1},{-1,-2},{-2,-1}};
	V[1] = {{1,1},{1,-1},{-1,1},{-1,-1}};
	
	dist[sy][sx][0]=0;
	queue<int> Q;
	Q.push(sy*1000+sx);
	while(Q.size()) {
		k=Q.front();
		Q.pop();
		int ct=k/1000000;
		int cy=k/1000%1000;
		int cx=k%1000;
		
		FORR(r,V[ct]) {
			int ty=cy+r.second;
			int tx=cx+r.first;
			if(tx<0 || ty<0 || ty>=H || tx>=W) continue;
			int tt=ct^(S[ty][tx]=='R');
			if(dist[ty][tx][tt]>dist[cy][cx][ct]+1) {
				dist[ty][tx][tt]=dist[cy][cx][ct]+1;
				Q.push(tt*1000000+ty*1000+tx);
			}
		}
	}
	
	x=min(dist[gy][gx][0],dist[gy][gx][1]);
	if(x>101010) x=-1;
	cout<<x<<endl;
	
}

まとめ

解法は自明なのだけど、これ系は毎度時間がかかる。
うまくライブラリにできないかな…。