Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-20SRM368, SRM369 (Practice)

SRM 368 JumpingBoard

|  SRM 368 JumpingBoard - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 368 JumpingBoard - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8245

  • 方針を検討
    • ダイクストラっぽいことをすればいいよね
    • 同じ所に戻ってきたら-1で
  • いやまて、それじゃダメだ
    • ある場所に到達するのに2つ以上の経路があると詰む
  • 別の方法を考える
    • 幅優先で書いて単純にステップ数が上限(2500ぐらい)を超えたら-1でいいのでは
  • サンプル通ったので出した
    • TLEした
    • ちゃんとメモ化再帰で書かないとダメでした
  • 計算量の見積もりが甘かった・・・
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class JumpingBoard {

	class State {
		int h, w;
		int step = 0;
		State(int i, int j, int s) {
			h = i;
			w = j;
			step = s;
		}
	}
	
	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, 1, 0, -1};
	int[][] done;
	int INF = 1000000;
	String[] board;
	int h, w;
	
	public int dfs(int r, int c) {
		if (r < 0 || c < 0 || c >= w || r >= h) {
			return 0;
		}
		if (done[r][c] >= 0) {
			return done[r][c];
		}
		if (board[r].charAt(c) == 'H') {
			return 0;
		}
		
		done[r][c] = INF;
		int ch = board[r].charAt(c) - '0';
		int max = 0;
		for (int d = 0 ; d < 4 ; d++) {
			int ty = r + dy[d] * ch;
			int tx = c + dx[d] * ch;
			max = Math.max(max, dfs(ty, tx) + 1);
		}
		done[r][c] = max;
		return max;
	}
	
	public int maxJumps(String[] b) {
		board = b;
		h = board.length;
		w = board[0].length();
		done = new int[h][w];
		for (int i = 0 ; i < h ; i++) {
			Arrays.fill(done[i], -1);
		}
		
		int c = dfs(0, 0);
		return (c > 1000000) ? - 1: c;
	}
}