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