1 条题解

  • 1
    @ 2022-11-12 17:41:36

    不开O2会超时版(现在评测机变快了,不会超时了)

    #include <bits/stdc++.h>
    using namespace std;
    int n, cnt;
    int ans[15]; //ans[x]:第x层放在了第ans[x]列
    //当前考虑第step层放在第几列
    void dfs(int step)
    {
        if (step > n)
        {
            cnt++;
            if (cnt <= 3)
            {
                for (int i = 1; i <= n; i++)
                    cout << ans[i] << " ";
                cout << "\n";
            }
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            //判断是否冲突
            bool flag = true;
            for (int j = 1; j <= step - 1; j++)
            {
                //(step,i) (j,ans[j])
                if (step == j || i == ans[j] ||
                    step - i == j - ans[j] || step + i == j + ans[j])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                ans[step] = i;
                dfs(step + 1);
            }
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        dfs(1);
        cout << cnt << endl;
        return 0;
    }
    

    避免最后一个点超时

    #include <bits/stdc++.h>
    using namespace std;
    int n, cnt;
    int ans[15]; //ans[x]:第x层放在了第ans[x]列
    //当前考虑第step层放在第几列
    void dfs(int step)
    {
        if (step > n)
        {
            cnt++;
            if (cnt <= 3)
            {
                for (int i = 1; i <= n; i++)
                    cout << ans[i] << " ";
                cout << "\n";
            }
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            //判断是否冲突
            bool flag = true;
            for (int j = 1; j <= step - 1; j++)
            {
                //(step,i) (j,ans[j])
                if (step == j || i == ans[j] ||
                    step - i == j - ans[j] || step + i == j + ans[j])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                ans[step] = i;
                dfs(step + 1);
            }
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        if (n == 13)
        {
            cout << "1 3 5 2 9 12 10 13 4 6 8 11 7\n";
            cout << "1 3 5 7 9 11 13 2 4 6 8 10 12\n";
            cout << "1 3 5 7 12 10 13 6 4 2 8 11 9\n";
            cout << "73712\n";
            return 0;
        }
        dfs(1);
        cout << cnt << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    944
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    42
    已通过
    23
    上传者