数独效实的伸见及POJ 2676-Sudoku(dfs+剪枝)

作者: [db:作者]

  1 #include

  2 #include

  3 #include

  4 #include

  5 #include

  6 #include

  7 #include

  8 #include

  9 #define inf 1<<25

  10 #define LL long long

  11 using namespace std;

  12 int row[10][10];

  13 int col[10][10];

  14 int map[10][10];

  15 int small[10][10];

  16 int f(int x,int y)

  17 {

  18 return 3*((x-1)/3)+(y-1)/3+1;

  19 }

  20 void init()

  21 {

  22 int i,j;

  23 char ch;

  24 memset(row,0,sizeof(row));

  25 memset(col,0,sizeof(col));

  26 memset(small,0,sizeof(small));

  27 for(i=1; i<=9; i++)

  28 {

  29 for(j=1; j<=9; j++)

  30 {

  31 scanf("%c",&ch);

  32 map[i][j]=ch-'0';

  33 if(map[i][j])

  34 {

  35 int k;

  36 k=f(i,j);

  37 row[i][map[i][j]]=1;

  38 col[j][map[i][j]]=1;

  39 small[k][map[i][j]]=1;

  40 }

  41 }

  42 getchar();

  43 }

  44 }

  45 int dfs(int x,int y)

  46 {

  47 if(x==10)

  48 return 1;

  49 int flag=0;

  50 if(map[x][y])

  51 {

  52 if(y==9)

  53 flag=dfs(x+1,1);

  54 else

  55 flag=dfs(x,y+1);

  56 if(flag)

  57 return 1;

  58 else

  59 return 0;

  60 }

  61 else

  62 {

  63 int k=f(x,y);

  64 for(int i=1; i<=9; i++)

  65 if(!row[x][i] && !col[y][i] && !small[k][i])

  66 {

  67 map[x][y]=i;

  68 row[x][i]=1;

  69 col[y][i]=1;

  70 small[k][i]=1;

  71 if(y==9)

  72 flag=dfs(x+1,1);

  73 else

  74 flag=dfs(x,y+1);

  75 if(!flag)

  76 {

  77 map[x][y]=0;


上一篇:我养的宠物龟 被婆儿子妈炖成父亲补养汤
下一篇:没有了