B、connect3题解
初见以为是一道十分复杂的组合数学计数问题,但后来发现范围很小,搜索即可。
场上遇到的困难:
1、终止情况的检测
1)白先手,白结束且落在X1,Y1结束
2)只能从下往上垒叠
3)满足横纵斜连续三个相同颜色游戏结束
情况其实是比较复杂的,如何确定在白落在X1,Y1之前游戏没有结束?判断游戏结束的函数该如何处理?这是在搜索策略的处理上不够强
2、对搜索状态节点存储
以前写过的搜索题,搜索状态节点还是很简单的,但该题的状态节点为一个矩阵,没有构造出好的状态节点

问题一的处理:
对于约束复杂的搜索题,可以将约束条件进行划分(组合数学思想)T=s1+s2+s3...我们在每个锁节点si处处理一个约束条件,处理完后判断是该返回,还是该继续,需要维护那些状态?改变哪些状态?该转移到哪个锁节点?如此一来复杂的约束搜索问题便变简单了(对于该题的约束划分策略可参考代码注释)[本质是构造一个状态机]

问题二的处理:
状态节点的结构,即为数据的结构。。本老咸鱼想到了两种策略
其一是可以想一想有什么数据结构能嵌合构造出搜索的状态节点,这一点是比较常规的。
其二是对于数字的性质的应用,这和组合数学、数论是密切相关的,众所周知数字与数字一旦组合,便可衍生无穷无尽的性质,利用这些数字之间的性质,可以借助数字的天然结构来十分巧妙的存储信息,有时能大大简化程序的代码量,这种策略的典型应用就是状压DP,用数字的二进制来存储大量状态节点,并可以利用数字的位运算(十分强大的数字性质应用)实现快速处理。对于本题,我们有两种颜色,16个空间点,数值都非常小,而long long的范围大体可以转化为64位二进制,即64个状态,自然而然我们可以想到利用long long数字的性质来便捷存储。 利用数字性质,可以用二进制的两位表示两种颜色,对于十六个空间点,即32位二进制表示整个矩阵的状态。这便是数字的强大之处,一个数字居然可以代表一个矩阵。

参考代码:

#include<stdio.h>
#include<map>
using namespace std; 
int a[6][6];//列(x)行y 
int cnt[5];//每一列垒叠到了哪个位置 
int X0,X1,Y1;
int ans;
//map范围  深搜计数法  键值记录技巧  (进制压缩 
map<long long,int> vis;
long long  judge1()
{
    long long sum=0; 
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            sum=sum<<2 |a[i][j];
        }
    }
    return sum; 
}

int judge2(int p)
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(j+2<=3&&a[i][j]==p&&a[i][j+1]==p&&a[i][j+2]==p)//行 
            return 1;
            if(i+2<=3&&a[i][j]==p&&a[i+1][j]==p&&a[i+2][j]==p)//列 
            return 1;
            if(i+2<=3&&j+2<=3&&a[i][j]==p&&a[i+1][j+1]==p&&a[i+2][j+2]==p)//左下
            return 1; 
            if(i-2>=0&&j+2<=3&&a[i][j]==p&&a[i-1][j+1]==p&&a[i-2][j+2]==p)//右下 
            return 1;
        }
    }
    return 0;
}

/*
深搜约束划分:
约束较复杂,划分为约束条件a:判断游戏是否结束  约束条件b:判断游戏结束时计数是否增加  约束条件c:从从下往上垒叠式搜索 
1、搜索基本步骤:搜索过的状态节点要剪枝   添加一个锁节点1  检测完锁节点1结束 

2、 约束条件a:游戏到达结束情况要返回   添加一个锁节点2 

约束条件b:白到X1Y1胜计数+1   因在锁节点2的内部,故在锁节点2的内部添加锁节点3
约束条件b检测完毕 锁节点3结束

约束条件a检测完毕 锁节点2结束 

搜索中:  约束条件c: 从下到上垒叠式搜索   锁节点4:循环时加以控制即可  搜索策略?采用回溯
锁节点4结束 
*/ 
void dfs(int p)
{
    //锁节点s1: 该矩阵状态若已搜索过,剪枝 ,若无,则标记该状态节点 
    long long t=judge1();
    if(vis[t])
    return ;
    vis[t]=1;
    //锁节点s1结束 
    //锁节点s2:判断游戏是否处于终止状态   终止状态需返回 
    if(judge2(1)||judge2(2)||a[X1][Y1])
    {
        //锁节点s3:判断是否白方胜利,若胜利计数+1 
        if(judge2(2)&&a[X1][Y1]==2)
        {
            ans++;
        }
        //锁节点s3结束 
        return ;//锁节点s2结束 
    }
    //锁节点s4: 确定下一步搜索:  搜索范围?4列从下往上垒叠,垒叠到哪一位置可以预处理
    //                            是否使用回溯?  使用,因为要遍历全部状态空间进行计数 
    for(int i=0;i<4;i++)
    {
        if(cnt[i]==4)
        continue;
        a[i][cnt[i]++]=p;
        dfs(3-p);
        a[i][--cnt[i]]=0;
    }
    //锁节点s4结束 
    return ;
}
int main()
{
    scanf("%d%d%d",&X0,&Y1,&X1);
    X0--,Y1--,X1--;
    a[X0][cnt[X0]++]=1;
    dfs(2); 
    printf("%d\n",ans);
}