八皇后（dfs+回溯）

重看了一下刘汝佳的白板书，上次写八皇后时并不是很懂，再写一次：

方法1：逐行放置皇后，然后递归；

代码：

 #include <bits/stdc++.h>

 #define MAXN 8

 #define ll long long

 using namespace std;

 ll ans=;

 int c[MAXN];

 void dfs(int cur)

 {

     if(cur==MAXN) ans++;   //***因为是逐行放置的，所以只要走到最后一行则肯定可行

     else

     {

         for(int i=; i<MAXN; i++)    //***尝试在第cur行的第i列放置皇后

         {

             int flag=;

             c[cur]=i;

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

             {

                 if(c[cur]==c[j]||c[cur]+cur==j+c[j]||c[cur]-cur==c[j]-j)  //**判断皇后是否会相互攻击

                 {

                     flag=;

                     break;

                 }

             }

             if(flag)

             {

                 dfs(cur+);  //***如果合法，继续递归

             }

         }

     }

 }

 int main(void)

 {

     dfs();

     cout << ans << endl;

     return ;

 }

方法2：思路和方法1差不多，区别是用二维数组vis[2][]来标记之前皇后的位置，判断是否会相互攻击

代码：

 #include <bits/stdc++.h>

 #define MAXN 8

 #define ll long long

 using namespace std;

 ll ans=;

 int c[MAXN], vis[][*MAXN];

 void dfs(int cur)

 {

     if(cur==MAXN) ans++;   //***因为是逐行放置的，所以只要走到最后一行则肯定可行

     else

     {

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

         {

             if(!vis[][i]&&!vis[][cur+i]&&!vis[][cur-i+MAXN])

             {

                 c[cur]=i;                        //***尝试将皇后放置在第cur行第i列

                 vis[][i]=vis[][cur+i]=vis[][cur-i+MAXN]=;  //**标记

                 dfs(cur+);                                 //**递归

                 vis[][i]=vis[][cur+i]=vis[][cur-i+MAXN]=; //**去除标记

             }

         }

     }

 }

 int main(void)

 {

     dfs();

     cout << ans << endl;

     return ;

 }

巴特西

八皇后（dfs+回溯）

最新文章

热门文章