poj 2676 Sudoku(dfs)

2019-11-08 02:20:02

字体：大中小

来源：转载

供稿：网友

用一个数组把空位记录下来，直接搜索就好了

#include <cstdio>#include <cstring>struct node{ int x,y;};node ns[100];int len;char g[10][10];bool flag;bool check(int k, int index){ int x = ns[index].x; int y = ns[index].y; int cx = (x/3)*3+1; int cy = (y/3)*3+1;//当前所在子矩阵的中心坐标 int mark = false; for(int i = 0; i < 9; ++i) { if(g[x][i] == k) { mark = true; break; } if(g[i][y] == k) { mark = true; break; } } if(mark) return false; if(g[cx][cy] == k || g[cx-1][cy-1] == k || g[cx-1][cy] == k || g[cx][cy-1] == k || g[cx+1][cy] == k || g[cx][cy+1] == k || g[cx-1][cy+1] == k || g[cx+1][cy-1] == k || g[cx+1][cy+1] == k) mark = true; if(mark) return false; return true;}void DFS(int index){ if(index == len) { flag = true; return; } for(int k = 1; k <= 9; ++k) { if(check(k+'0',index)) { g[ns[index].x][ns[index].y] = k+'0'; DFS(index+1); if(flag) return; g[ns[index].x][ns[index].y] = '0'; } }}int main(){ int t; scanf("%d",&t); while(t--) { flag = false; len = 0; for(int i = 0; i < 9; ++i) for(int j = 0; j < 9; ++j) { scanf(" %c",&g[i][j]); if(g[i][j] == '0') { ns[len].x = i; ns[len].y = j; ++len; } } DFS(0); for(int i = 0; i < 9; ++i) { for(int j = 0; j < 9; ++j) PRintf("%c",g[i][j]); printf("/n"); } } return 0;}

上一篇：Linux学习笔记------认识与学习bash

下一篇：LeetCode 55. Jump Game