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; }