# 龙神的宝物## 题目描述小申和小广历经千辛万苦终于找到了传说中的龙神殿。大殿里面有一个$33$的棋盘$9$个格子起初每个格子均没有放置棋子。现在小申得到了一盒黑棋小广得到了一盒白棋。两人轮流行动每次可以将一个棋子放入棋盘的格子内。若某个人放置一个棋子后该棋子与另外两个棋子不论是谁放置的都可以达成三子连线即三个棋子连成一条线水平、垂直、主副对角线均可则该人获胜。获胜的人也将得到龙神的宝物。小申总

#include<bits/stdc++.h>
using namespace std;
int x,y;
string h="hhhh ye",n="oh  no";//全局变量，方便输出
int g[10][10];
int dg[10][10],udg[10][10],row[10],col[10],f[10][10][10][10];
//g存储棋盘情况，dg、udg、row、col分别表示主、副对角线、行、列是否已有棋子，f表示记忆化
int dfs(int p,int q,int t,int k,int u)
{
    if(f[p][q][t][k]!=-1) return f[p][q][t][k];//记忆化
    if(p>=3||q>=3||t>=3||k>=3) return 0;//边界判断
    if(u%2==1)//小申
    {
        if((p==t&&q==k&&p+t==4&&q+k==4)||dg[p][q]||udg[q][p]||row[p]||col[q])//是否存在连线，是否已有棋子
            return dfs(p,q,t,k,u+1);//如果已有，跳过
        if(dfs(p,q+1,t,k,u+1)||dfs(p+1,q,t,k,u+1)||dfs(p,q,t+1,k,u+1)||dfs(p,q,t,k+1,u+1))
            return f[p][q][t][k]=1;//如果小申可以获胜，记录，并返回1
    }
    if(u%2==0)//小广
    {
        if((p==t&&q==k&&p+t==4&&q+k==4)||dg[p][q]||udg[q][p]||row[p]||col[q])//是否存在连线，是否已有棋子
            return dfs(p,q,t,k,u+1);//如果已有，跳过
        if(dfs(p,q+1,t,k,u+1)&&dfs(p+1,q,t,k,u+1)&&dfs(p,q,t+1,k,u+1)&&dfs(p,q,t,k+1,u+1))
            return f[p][q][t][k]=0;//如果小广不可能获胜，记录，并返回0
    }
}
int main()
{
    memset(f,-1,sizeof(f));
    cin>>x>>y;
    g[x][y]=1;//小申第一个棋子
    row[x]=1;//行有棋子
    col[y]=1;//列有棋子
    if(x==y)//主对角线有棋子
        dg[x][y]=1;
    if(x+y==4)//副对角线有棋子
        udg[x][y]=1;
    if(dfs(0,0,0,0,1)==1)//小申获胜
        cout<<h;
    else//小广获胜或平局
        cout<<n;
    return 0;
}
``