point10 TLE 警钟撅烂
查看原帖
point10 TLE 警钟撅烂
590283
lunatics楼主2024/6/25 14:36

如果point10 TLE且没有使用全局数组,注意引用传参

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> vec;
int solve_count;

void dfs(int &level, vector<bool> &diagonal_lr, vector<bool> &diagonal_rl, vector<bool> &col) {
    if(level == n + 1) {
        solve_count++;
        if(solve_count <= 3) {
            for(auto i : vec) {
                cout<<i<<" ";
            }
            cout<<endl;
        }
        return;
    }
    for(register int i = 1; i <= n; i++) {
        if(!diagonal_lr[i - level + n - 1] and !diagonal_rl[i + level - 2] and !col[i - 1]) {
            diagonal_lr[i - level + n - 1] = diagonal_rl[i + level - 2] = col[i - 1] = true;
            vec.push_back(i);
            level++;
            dfs(level, diagonal_lr, diagonal_rl, col);
            level--;
            vec.pop_back();
            diagonal_lr[i - level + n - 1] = diagonal_rl[i + level - 2] = col[i - 1] = false;
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    vector<bool> diagonal_lr(2*n - 1);
    vector<bool> diagonal_rl(2*n - 1);
    vector<bool> col(n);
    int level = 1;
    dfs(level, diagonal_lr, diagonal_rl, col);
    cout<<solve_count<<endl;
    return 0;
}

原来参数压栈这么耗时间:(

2024/6/25 14:36
加载中...