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