苗火 Nicholas

Description

Upwinder最近喜欢上了一款古老的起源于Scandinavia(斯堪迪纳维亚半岛)的小游戏。具体的游戏规则如下：

1. 棋盘设定

棋盘的大小为8行8列，有两个玩家：狐狸和小狗。初始的时候有4只小狗被放置在棋盘最上边一行的4个黑色格子里；而1只狐狸被放在最下边一行的某个黑色格子里。以棋盘左上角为原点，向下为行的正方向，向右为列的正方向，从1开始给每一个格子编号.

2. 移动规则

(1) 两个玩家轮流下棋。

(2) 狐狸每轮可以斜着向上或斜着向下移动至相邻的一个空格子，只能移动一步；

(3) 小狗每轮只能斜着向下移动至相邻的一个空格子，只能移动一只，且只能移动一步；

(4) 显然根据移动规则棋盘中只有黑色的格子才能放棋子

3. 游戏目标

狐狸与小狗的目标是不同的。

(1) 如果小狗将狐狸围住致使其无法移动(包括围在边界)，那么小狗获胜。

(2) 如果狐狸到达了棋盘最上方一行的任意一个黑色格子，那么狐狸获胜；

特别的，游戏不存在平局或死局，而且如果4只小狗均无法移动，则狐狸可以一直移动直至取胜。

现在告诉你游戏过程中的某一个局面，你能帮Upwinder判断如果狐狸与小狗均采取最优策略的话，谁能取得最后的胜利吗？

Input

第一行一个数字T表示接下来有T(T<=3000)种局面。

对于每一种局面，由三行数据组成，其中：

第一行为整数0或1。0代表当前狐狸掌握棋权，1代表当前小狗掌握棋权。

第二行为两个整数，以空格分隔，依次是狐狸在棋盘上的行坐标Fr和列坐标Fl。

第三行为八个整数，以空格分隔，依次是第一只小狗的行坐标Dr1,列坐标Dl1……以此类推。

Output

对于每一种局面，仅输出一行。

如果狐狸能够取胜，请输出“Fox win”(不含引号)

如果小狗能够取胜，请输出“Dog win”(不含引号)

#include <stdio.h>

typedef struct{
        int x;
        int y;
}P;

int chess(int s,  P *f, P *d){
        int i,j;

        if(f->x < 1 || f->x > 8 || f->y < 1 || f->y > 8){
                return -1;
        }
        for(i=0; i<4; i++){
                if(d[i].x < 1 || d[i].x > 8 || d[i].y < 1 || d[i].y > 8){
                        return -1;
                }
                if(d[i].x == f->x && d[i].y == f->y){
                        return -1;
                }
                for(j=0;j<4;j++){
                        if(i != j && d[j].x == d[i].x && d[j].y == d[i].y){
                                return -1;
                        }
                }
        }

        for(i=0;i<4;i++){
                if(f->y > d[i].y){
                        break;
                }
        }
        if(i==4){
                return 0;
        }
        if(s==0){
                f->x--; f->y--;
                i = chess(1, f, d); if(i>=0) return i;
                f->x; f->y+=2;
                i = chess(1, f, d); if(i>=0) return i;
                f->x+=2; f->y;
                i = chess(1, f, d); if(i>=0) return i;
                f->x; f->y-=2;
                i = chess(1, f, d); if(i>=0) return i;
                f->x--; f->y++;
                //fox cannot move to any other point, game over.
                if(f->y == 1){
                        return 0;
                }else{
                        return 1;
                }
        }else{
                for(j=0; j<4; j++){
                        d[j].x++; d[j].y++;
                        i = chess(0, f, d); if(i>0) return i;
                        d[j].x-=2; d[j].y;
                        i = chess(0, f, d); if(i>0) return i;
                        d[j].x++; d[j].y--;
                }
                //dog cannot move to any other point, fox is the leader.
                return chess(0, f, d);
        }
}
void main(){
        int t,s,ret;
        P f,d[4];
        scanf(" %d", &t);
        while(t--){
                scanf(" %d", &s);
                scanf(" %d %d", &f.x, &f.y);
                scanf(" %d %d %d %d %d %d %d %d", &d[0].x, &d[0].y,  &d[1].x, &d[1].y, &d[2].x, &d[2].y, &d[3].x, &d[3].y);
                ret = chess(s, &f, d);
                if(ret == 0){
                        printf("Fox win\n");
                }else{
                        printf("Dog win\n");
                }
        }
}