AOJ-0122 : Summer of Phyonkichi

問題概要

10*10マスの中にカエルがいる。カエルは周囲のある12箇所に移動できる。訪ねるべき3*3の範囲がいくつか与えられるので、それをすべて順番に訪ねることができるか判定する問題。

解法

簡単なDP。

acceptされたコード

import std.algorithm, std.stdio, std.range;

int N;
immutable W = 10, M = 12;
immutable dy = [-2,-2,-2,-1,-1,0,0,1,1,2,2,2], dx = [-1,0,1,-2,2,-2,2,-2,2,-1,0,1];
immutable ddy = [-1,-1,-1,0,0,0,1,1,1], ddx = [-1,0,1,-1,0,1,-1,0,1];
int[] ys, xs;

void main(){
	for(;init;){
		writeln(solve ? "OK" : "NA");
	}
}

bool init(){
	ys = []; xs = [];
	int y, x;
	scanf("%d%d", &y, &x);
	ys ~= y; xs ~= x;
	if(y == 0 && x == 0){
		return false;
	}
	scanf("%d", &N);
	foreach(_; 0..N){
		scanf("%d%d", &y, &x);
		ys ~= y; xs ~= x;
	}
	return true;
}

bool solve(){
	auto dp = new bool[][](N + 1, 9);
	dp[0][4] = true;

	foreach(i; 0..N){
		foreach(j; 0..9)if(dp[i][j]){
			foreach(k; 0..M){
				int ny = ys[i] + ddy[j] + dy[k], nx = xs[i] + ddx[j] + dx[k];
				if(0<=ny && ny<W && 0<=nx && nx<W)foreach(l; 0..9){
					if(ys[i+1] + ddy[l] == ny && xs[i+1] + ddx[l] == nx){
						dp[i+1][l] = true;
					}
				}
			}
		}
	}

	return count(dp[N], true) > 0;
}