SRM 368 250pt: JumpingBoard

TopCoder

問題概要

２次元のボード(W*H(W,H<50))が与えられる。各マスは、穴か数字が書いてあるかのどちらかである。ある点からスタートして、今居るマスが数字ならその数字の分だけ4方向のいずれかへ移動することができる。マスの外に出たり、穴へ跳んだときはそこで終了する。最長で何回飛ぶことができるか求める問題。

考えたこと

  • 何これただのBFS？これだから昔のSRMは…。
  • 当然落ちる。そうかこれってDAGの最長パスか。
  • DAGかどうかの判定して、DAGでないなら即座に-1を返してそうでないなら普通にメモ化再帰で行ける。
  • DAGかどうかの判定ってどう書くのが楽なんだろう。強連結成分分解して成分の個数とノードの個数比較するのが計算量的には最適な気がするけど逆辺とか構成するの面倒だし…。
  • トポロジカルソートの途中で自分よりトポロジカル順序の小さい所に行けたら非DAG？
  • いやいや違う。一回トポロジカルソートした後でやらなきゃか。
  • 書く。最後のサンプルが通らない。
  • 到達可能でない所で有向閉路があっても関係ないのか。そりゃそうだ。
  • 通った。

practiceで通ったコード

計算量O(W*H)。

#include <algorithm>
#include <queue>
#include <cctype>
using namespace std;

const int MAX_N = 55;

int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};
int H, W;

int tp_counter;
int memo[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

vector<string> board;
vector< pair<int,int> > rev_graph[MAX_N][MAX_N];

struct JumpingBoard {

	int maxJumps(vector <string> _board) {
		board = _board;
		H = board.size();
		W = board[0].length();

		//DAGチェック
		tp_counter = H*W-1;
		dfs(0,0);
		for(int y=0; y<H; y++){
			for(int x=0; x<W; x++)if(visited[y][x]){
				if(isdigit(board[y][x]))for(int k=0; k<4; k++){
					int ny = y + dy[k]*(board[y][x]-'0'),
						nx = x + dx[k]*(board[y][x]-'0');
					if(0<=ny && ny<H && 0<=nx && nx<W && memo[ny][nx] < memo[y][x]){
						return -1;
					}
				}
			}
		}

		memset(visited, 0, sizeof(visited));

		return rec(0,0);
	}

	int rec(int y, int x){
		if(!(0<=y && y<H && 0<=x && x<W)){
			return 0;
		}

		//メモ化処理
		if(visited[y][x]){
			return memo[y][x];
		}
		visited[y][x] = true;

		int& ret = memo[y][x];
		ret = 0;

		if(board[y][x] == 'H'){
			return ret = 0;
		}

		//再帰探索
		if(isdigit(board[y][x]))for(int k=0; k<4; k++){
			int ny = y + dy[k]*(board[y][x]-'0'),
				nx = x + dx[k]*(board[y][x]-'0');
			ret = max(ret, rec(ny,nx) + 1);
		}

		return ret;
	}

	void dfs(int y, int x){
		visited[y][x] = true;
		if(isdigit(board[y][x]))for(int k=0; k<4; k++){
			int ny = y + dy[k]*(board[y][x]-'0'),
				nx = x + dx[k]*(board[y][x]-'0');
			if(0<=ny && ny<H && 0<=nx && nx<W && !visited[ny][nx]){
				dfs(ny,nx);
			}
		}
		memo[y][x] = tp_counter--;
	}
};

他の人の解法

答えの上限がW*Hくらいなので、ベルマンフォードっぽく書いてる人が多数いた。というか、辺のコストを全部-1に置き換えてみたらこれは最短経路問題そのものだ。