Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:附上强剪条件In Reply To:附上强剪条件 Posted by:damacheng009 at 2010-10-26 15:49:26 > 1.遍历当前所有的空格: > 1)如果发现某个空格1-9都放不下,则返回上一层。 > 2)如果只有1个数可以填,则此空格就只能填上此数,这样就消除一个空格。 > 3)如果有2个以上的数可以填,则不做处理。 > > 2.遍历当前所有的空格: > 1)如果发现在某行中,某个数字不能存在于该行的任一个空格中,则返回上一层。 > 2)如果发现某个空格所在的行中,某个数字只能填在此空格中,则直接填上,这样就 > 消除一个空格;有2个以上则不做处理。 > > 3.同2,把2中的行替换为列。 > > 4.同2,把2中的行替换为子数独。 > > 实践证实:实现1,2,3点即可AC。 > > 附上DFS函数供有需要的同学参考: > bool dfs() { > if(space_num <= 0) return true; > > if(set_grid_only() == false) return false; > if(set_row_only() == false) return false; > if(set_col_only() == false) return false; > > if(space_num <= 0) return true; > > int c_space_num; > int c_map[9][9]; > bool c_tbl[9][9][9]; > c_space_num = space_num; > memcpy(c_map, map, sizeof(map)); > memcpy(c_tbl, tbl, sizeof(tbl)); > > int next_r, next_c; > bool flag = false; > for(int r = 0; r < 9; ++r) { > for(int c = 0; c < 9; ++c) { > if(map[r][c] == SPACE) { > next_r = r; > next_c = c; > flag = true; > goto _out; > } > } > } > > _out: > if(flag) { > for(int k = 0; k < 9; ++k) { > if(tbl[next_r][next_c][k] == VACANT) { > init(next_r, next_c, k); > space_num--; > if(dfs()) return true; > else { > space_num = c_space_num; > memcpy(map, c_map, sizeof(map)); > memcpy(tbl, c_tbl, sizeof(tbl)); > } > } > } > } > > return false; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator