Beta Round #63-D: Dot
解法
状態数が400^2で、ある状態からの遷移が20通りなので普通にメモ化探索するだけ。反射は打ち消せるので無意味。
感想
状態数が微妙に少なかったのと配列のindexを座標で持っておくのが面倒だったのでmapでメモ化した。もちろん座標を平行移動して普通の配列でメモ化してもよい。というか多分そっちの方が楽だった(計算量もより安全になるし)。
#include <cstdio> #include <map> using namespace std; int X, Y, N, d; int dx[30], dy[30]; map<int, map<int, bool> > visited; map<int, map<int, bool> > win; bool solve(int x, int y){ if(x*x + y*y > d*d){ return true; } if(visited[x][y]){ return win[x][y]; } visited[x][y] = true; for(int i=0; i<N; i++){ int ny = y + dy[i], nx = x + dx[i]; if(!solve(nx,ny)){ return win[x][y] = true; } } return win[x][y] = false; } int main(){ scanf("%d%d%d%d",&X,&Y,&N,&d); for(int i=0; i<N; i++){ scanf("%d%d",dx+i,dy+i); } puts(solve(X,Y)?"Anton":"Dasha"); return 0; }