Yao Lirong's Blog

P1219 八皇后

NOI
2019/06/16

题目来源：洛谷P1219 八皇后

我的解法

自己的程序出现的几个问题：

  1. 对角线表达式太过复杂，各层绝对值都可以简化，应该相信大部分情况下复杂的都是错误的
  2. 不需要记录这一行放没放过棋子，因为我们是按照一行一行的顺序放过来的，上一行必定有棋子，下一行必定无棋子
  3. 注意初始化的部分，一开始就是把循环语句里写成了 NE_SW[i]=true; NE_SW[i+1]=true 导致了错误而且一直没检查出来
  4. 最后那个存储 solution 的地方还是有问题，如果找到了某一行的一个解并且继续向下搜寻这一行的其他解的话，会出现不存储前面几行棋子位置的问题，没想到解决方法只能在输出的地方做了些操作
  5. 大部分标解中dfs只有一个参数就是行数x然后对于每个x进行for循环枚举纵坐标y，我这样的做法也可以
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool board[14][14],col[14],line[14],NE_SW[26],NW_SE[26]; int n,ans,solution[3][15];
bool flag(int, int);
void dfs(int, int);
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) {col[i]=true; line[i]=true; NE_SW[i]=true; NW_SE[i]=true; NE_SW[i+n]=true; NW_SE[i+n]=true;}/// 这个地方初始化一定要注意
    dfs(1,1);
    for(int i=0;i<3;i++){
        for(int j=1;j<=n;j++){
            if(solution[i][j]==0) solution[i][j]=solution[i-1][j];
            cout<<solution[i][j]<<" ";

        }
        cout<<endl;
    }
    cout<<ans;
}
bool flag(int x,int y)///判定这个点能不能放棋子
{
    if(col[x]&&line[y]){if(NE_SW[x+y-1]){
        if( y<=x && NW_SE[n-int(abs(x-y))] ) return true;
        else if( y>x && NW_SE[n+int(abs(x-y))] ) return true;
        //cout<<"最后一个对角线出了问题"<<endl;
    }//cout<<"第一个对角线出了问题"<<endl;
    }
    //cout<<"x,y有问题"<<endl;
    return false;
}
void dfs(int x,int y)
{
    ///cout<<"function called at"<<x<<" "<<y<<endl;
    if(flag(x,y)){
        //if(x==n) ans++;
        if(ans<=3) solution[ans][x]=y;

        ///cout<<endl<<"one unit placed at"<<x<<" "<<y<<endl<<endl;
        col[x]=false;
        line[y]=false;
        if(y<=7-x) NE_SW[x+y-1]=false; ///左上角部分的 右上-左下对角线
            else NE_SW[x+y-1]=false; /// 右下角部分的 右上-左下对角线
        if(y<=x) NW_SE[n-int(abs(x-y))]=false; ///右上角部分的 左上-右下对角线
            else NW_SE[n+int(abs(x-y))]=false; ///左下角部分 左上-右下对角线

        if(x==n) {ans++;} ///cout<<"-------------"<<endl<<"one solution found, total solution is now "<<ans<<endl<<"-------------"<<endl;}
        else dfs(x+1,1);

        col[x]=true;
        line[y]=true;
        if(y<=7-x) NE_SW[x+y-1]=true; ///左上角部分的 右上-左下对角线
            else NE_SW[x+y-1]=true; /// 右下角部分的 右上-左下对角线
        if(y<=x) NW_SE[n-int(abs(x-y))]=true; ///右上角部分的 左上-右下对角线
            else NW_SE[n+int(abs(x-y))]=true; ///左下角部分 左上-右下对角线
        ///cout<<"value changed back at"<<x<<" "<<y<<endl;

    }

    if(y<n) dfs(x,y+1);
}

更可读的代码以及问题优化

  1. 优化了对角线的表达
  2. 优化了答案位置的记录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool col[14],line[14],NE_SW[26],NW_SE[26]; int n,ans=0,solution[14]; /// col[x] line[y]
/// NE_SW 右上向左下方向的对角线，从左上角(1,1)为第一条，第二条是(2,1)-(1,2)
/// NW_SE 左上到右下方向的对角线，从右上角(1,n)为第一条，第二条是(n-1,1)-(n,2)
void dfs(int,int);
bool flag(int,int);
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) {col[i]=true; line[i]=true; NE_SW[i]=true; NW_SE[i]=true; NE_SW[i+n]=true; NW_SE[i+n]=true;}
    dfs(1,1);
    cout<<ans;
    return 0;
}
bool flag(int x,int y)
{
    return col[x]&&line[y]&&NE_SW[x+y]&&NW_SE[n+y-x];
}
void dfs(int x,int y)
{
    if(flag(x,y)){
        solution[x]=y;///注意这个地方特别精髓，因为如果我们每个答案都开新的一行数组记录的话有可能会出现上面问题4说的情况，所以我们只需要每次覆盖记录就好了，反正x永远是按从上到下的顺序来的
        //col[x]=false; line[y]=false; NE_SW[x+y]=false; NW_SE[n+y-x]=false;
        col[x]=!col[x]; line[y]=!line[y]; NE_SW[x+y]=!NE_SW[x+y]; NW_SE[n+y-x]=!NW_SE[n+y-x];
        ///注意 !col[x] 只是表达 col[x] 取反的一个值，只有 col[x]=!col[x] 才能给原波尔值赋值为它的反
        if(x==n){///最后一行也被填好了，我们得到一个解
            ans++;
            if(ans<=3){
                for(int i=1;i<=n;i++) cout<<solution[i]<<" ";
                cout<<endl;
            }
        }
        else dfs(x+1,1);///还不到最后一行的话就接着去找下一行

        ///回溯：拿走刚刚放下的棋子
        //col[x]=true; line[y]=true; NE_SW[x+y]=true; NW_SE[n+y-x]=true;
        col[x]=!col[x]; line[y]=!line[y]; NE_SW[x+y]=!NE_SW[x+y]; NW_SE[n+y-x]=!NW_SE[n+y-x];
    }
    ///如果这个位置不符合条件(flag(x,y)==false)/这个位置符合条件的情况已经被全部枚举了(flag(x,y)==true) 那么我们就可以去找本行的下一个位置是否满足条件
    if(y<n) dfs(x,y+1);
}

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/P1219%20%E5%85%AB%E7%9A%87%E5%90%8E/

Publish date：June 16th 2019, 12:00:00 am

Update date：June 27th 2019, 8:35:52 pm

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. 我的解法
  2. 2. 更可读的代码以及问题优化
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book