WUPC2nd F - 僕は宇宙人

問題

日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_06）

制約条件

N, M≦100
L≦100

方針

dp[何文字目まで作ったか][y座標][x座標][直前の方向] := 最小コストとしてDP.

次の文字がどこで出てくるか（get関数）を、毎回愚直に調べるとTLEする（と思った）。
メモ化しておけば、一回あたりの呼び出しはO(1)になるので、メモ化すればよい。

実際には次の文字が出てくる場所を愚直に探しても間に合った模様。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int h, w, n;
int next[100][100][26][4];
int dp[110][100][100][4];
string msg, in[100];
 
int get(int y, int x, int d, char c){
	if(y < 0 || y >= h || x < 0 || x >= w) return -2;
	int &res = next[y][x][c - 'a'][d];
	if(res != -1) return res;
	if(in[y][x] == c) return res = y * 100 + x;
	res = get(y + dy[d], x + dx[d], d, c);
	if(res < 0) return res;
	return res;
}
 
int main(){
	cin >> h >> w >> n;
	cin >> msg;
	rep(i, h) cin >> in[i];
	
	memset(next, -1, sizeof(next));
	rep(k, n + 1) rep(i, h) rep(j, w) rep(d, 4) dp[k][i][j][d] = k == 0 ? 0 : inf;
	
	rep(pos, n) rep(i, h) rep(j, w) rep(d, 4) if(dp[pos][i][j][d] != inf){
		
		rep(k, 4) if(d != k){
			int xy = get(i + dy[k], j + dx[k], k, msg[pos]);
			if(xy < 0) continue;
			
			int y = xy / 100, x = xy % 100;
			int cost = dp[pos][i][j][d] + abs(i - y) + abs(j - x);
			dp[pos + 1][y][x][k] = min(dp[pos + 1][y][x][k], cost);
		}
	}
	int ans = inf;
	rep(i, h) rep(j, w) rep(d, 4) ans = min(ans, dp[n][i][j][d]);
	
	cout << (ans == inf ? -1 : ans) << endl;
	return 0;
}