阅读背景:

【NOIP2009提高组T4】靶形数独-DFS剪枝+位运算优化

来源:互联网 

测试地址:靶形数独

做法:最朴素的DFS耗时较大,所以我们来想想应该如何优化。

如果每次都用9次运算来求一行,一列和一个九宫格中填了哪些数,时间开销显然很大。于是,我们可以用位运算来解决这个问题,这样就可以把状态压缩成用1次运算就可以求出这些东西。用line[i],column[i]表示第i行和第i列的状态(注意,为了计算方便,我们的行和列都以0~8编号),这里的状态是指已填了哪些数。如果第i行里填了数字j,那么line[i]转换成二进制数后从右往左第j位就为1。然后,用block[i][j]表示九宫格(包含(i*3,j*3),(i*3,j*3+1),(i*3,j*3+2),如果每




你的当前访问异常,请进行认证后继续阅读剩余内容。

分享到: