#8 1.00s 求优化！

P1219 [USACO1.5] 八皇后 Checker Challenge

SmartCirno @ 2024-05-22 13:49:41

#include <iostream>
using namespace std;
int n,ans,m[14][14];
bool check(int x,int y) // 判断m[x][y]是否能放 
{
    for(int i=1;i<=n;i++)if(m[i][y]==1&&i!=x)return false; // 列
    for(int j=1;j<=n;j++)if(m[x][j]==1&&j!=y)return false; // 行
    for(int i=x,j=y;i>0&&j<=n;i--,j++)if(m[i][j]==1&&(i!=x&&j!=y))return false; // 右上对角线 
    for(int i=x,j=y;i<=n&&j<=n;i++,j++)if(m[i][j]==1&&(i!=x&&j!=y))return false; // 右下对角线 
    for(int i=x,j=y;i>0&&j>0;i--,j--)if(m[i][j]==1&&(i!=x&&j!=y))return false; // 左上对角线 
    for(int i=x,j=y;i<=n&&j>0;i++,j--)if(m[i][j]==1&&(i!=x&&j!=y))return false; // 左下对角线 
    return true;
}
void output_m()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<m[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
void dfs(int a,int s)
{
    if(s==n)
    {
        //output_m();
        ans++;
        if(ans>3)return;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(m[i][j])
                {
                    cout<<j<<" ";
                    break;
                }
            }
        }
        cout<<endl;
        return;
    }
    for(int j=1;j<=n;j++)
    {
        if(check(a,j))
        {
            m[a][j]=1;
            dfs(a+1,s+1);
            m[a][j]=0;
        }
    }
}

int main()
{
    cin>>n;
    dfs(1,0);
    cout<<ans;
    return 0;
}

by lovely_codecat @ 2024-05-22 14:06:31

把所有endl改成'\n'即可

by SmartCirno @ 2024-05-22 14:11:42

@lovely_codecat 负优化

by CuteChat @ 2024-05-22 14:26:14

没有必要这么写 check，记录四个数组（哈希表） a,b,c,d，如果当前的位置是 (x,y)，如果 a_x, b_y, c_{x+y}, d_{x-y+n} 是存在的，就放弃当前位置，否则将 a_x, b_y, c_{x+y}, d_{x-y+n} 加入，再递归，回溯的道理相同。

by thehanged @ 2024-06-05 18:40:38

主要是判断对角线的问题

我的做法是正对角线映射的下标是x + i，反对角线是n + x - i

ac代码

#include <iostream>
#include <vector>
using namespace std;

const int N = 20;
bool col[N], dg[2 * N], udg[2 * N];
vector<int> path;
int n, cnt;

/// 枚举每行，搜索皇后可以放在哪列
void dfs(int x){
    if(x == n + 1){
        if(cnt < 3){
            for(auto& i : path){
                cout << i << " ";
            }
            cout << endl;
        }
        cnt ++;
        return ;
    }

    for(int i = 1; i <= n; ++ i){
        if(col[i] || dg[x + i] || udg[n + x - i]) continue;
        col[i] = dg[x + i] = udg[n + x - i] = true;
        path.push_back(i);
        dfs(x + 1);
        path.pop_back();
        col[i] = dg[x + i] = udg[n + x - i] = false;
    }
}

int main(){
    cin >> n;
    dfs(1);

    cout << cnt << endl;
}