HDU 1426(数独 DFS)

题意是完成数独。

记录全图，将待填位置处填 0，记录下所有的待填位置，初始化结束。在每个待填位置处尝试填入 1 - 9，若经过判断后该位置可以填入某数字，则继续向下填下一个位置，

回溯时把待填位置重新赋值为 0，总之就是深搜的思想。

要注意存数时是从 0 位置存到 8 位置，而不是从 1 位置存到 9 位置，因为这样在后面判断是否满足 3*3 的小九宫格要求时可以直接用坐标乘以 3 再除以 3 的方法到达小九

宫格的左上角位置，便于遍历小九宫格。

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 char c;

 int cnt,cur,cas,f,mp[][];

 struct node

 {

     int x,y;

 }q[];

 bool judge(int n,int cur)

 {

     for(int i = ; i < ; ++i)

     {

         if(mp[q[cur].x][i] == n || mp[i][q[cur].y] == n)

             return false;

     }

     int x = q[cur].x/*;

     int y = q[cur].y/*;

     for(int i = ; i < ; ++i)

         for(int j = ; j < ; ++j)

         {

             if(mp[x+i][y+j] == n)

                 return false;

         }

     return true;

 }

 void out()

 {

     for(int i = ; i < ; ++i)

     {

         for(int j = ; j < ; ++j)

         {

             if(j) printf(" ");

             printf("%d",mp[i][j]);

         }

         puts("");

     }

 }

 void dfs(int cur)

 {

     if(cur == cnt)

     {

         out();

         f = ;

     }

     else

     {

         for(int i = ; i <= &&!f; ++i)

         {

             if(judge(i,cur))

             {

                 mp[q[cur].x][q[cur].y] = i;

                 dfs(cur+);

                 mp[q[cur].x][q[cur].y] = ;

             }

         }

     }

 }

 int main()

 {

     while(cin >> c)

     {

         cnt = ;

         if(c=='?')

         {

             q[cnt].x = ;

             q[cnt++].y = ;

             mp[][] = ;

         }

         else mp[][] = c-'';

         for(int i = ; i < ; ++i)

         {

             cin >> c;

             if(c=='?')

             {

                 q[cnt].x = ;

                 q[cnt++].y = i;

                 mp[][i] = ;

             }

             else mp[][i] = c-'';

         }

         for(int i = ; i < ; ++i)

             for(int j = ; j < ; ++j)

             {

                 cin >> c;

                 if(c=='?')

                 {

                     q[cnt].x = i;

                     q[cnt++].y = j;

                     mp[i][j] = ;

                 }

                 else mp[i][j] = c-'';

             }

         f = ;

         if(cas++) puts("");

         dfs();

     }

     return ;

 }

对于九宫格问题还可以用舞蹈链的方法，但水平有限，没有掌握...... 有兴趣者请移步：https://www.cnblogs.com/grenet/p/3163550.html

巴特西

HDU 1426(数独 DFS)

最新文章

热门文章