测试地址:靶形数独
做法:最朴素的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),如果每