首页 > 代码库 > 【USACO】checker

【USACO】checker

2024-07-04 15:45:34   228人阅读

一看题目 经典的8皇后问题 不过是皇后数量可变而已 不用想 回溯法。 需要个生成每次可选择序列的函数， 在存储可选择的序列时按照先大后小的顺序排的。这样每次找最小和去掉最小都很方便，只要有个记录数量的变量 每次减1就好了。  写完后，居然悲剧了。 在皇后数量达到13时， 在自己电脑上跑 内存溢出了 在评分系统上超时了。需要优化。 

#include <stdio.h>
//k计算第几层从0开始 x已经摆好的位置 S存放产生的位置 l存放产生的数量 N一共有多少位置可以选择
int calculate(int k, int * x, int *S, int * l, int N)
{
    int i, j;
    int flag;
    *l = 0;
    for(i = N; i >= 1; i--) //大数在前面
    {
        flag = 1;
        for(j = 0; j <= k - 1; j++)
        {
            if(i == x[j] || i - x[j] == k - j  || x[j] - i == k - j )
            {
                flag = 0;
            }
        }
        if(flag == 1)
        {
            S[*l] = i;
            (*l)++;
        }
    }
    return 0;
}

int BackTrack(int N, int (*ans)[13], int * anum)
{
    *anum = 0;
    int i, j, k;
    int x[13];
    int S[13][13] = {0};
    int l[13] = {0};
    for(i = N - 1; i >= 0;  i--) //大数放前面
    {
        S[0][i] = N - i;
    }
    l[0] = N;
    k = 0;
    do{
        while(l[k] != 0)
        {
            x[k] = S[k][l[k] - 1]; //取最小的
            l[k]--;
            if(k < N - 1)
            {
                k++;
                calculate(k, x, S[k], &l[k], N);
            }
            else
            {
                for(i = 0; i < N; i++)
                {
                    ans[*anum][i] = x[i];
                }
                (*anum)++;
            }
        }
        k--;
    }while(k != -1);
    return 0;
}

int main()
{
    FILE *in, *out;
    in = fopen("checker.in", "r");
    out = fopen("checker.out", "w");

    int N;
    int ans[30000][13];
    int anum;
    fscanf(in, "%d", &N);
    BackTrack(N, ans, &anum);

    int i, j;
    for(i = 0; i <= 2; i++)
    {
        for(j = 0; j < N - 1; j++)
        {
            fprintf(out, "%d ", ans[i][j]);
        }
        fprintf(out, "%d\n", ans[i][N - 1]);
    }
    fprintf(out, "%d\n", anum);
    return 0;
}

 -------------------------------------

优化了一下计算新一层可能产生的数的算法 把calculate中嵌套的两个循环分开了（通过少量内存的代价）通过了测试 很开心啊~

#include <stdio.h>
#include <stdlib.h>
//k计算第几层从0开始 x已经摆好的位置 S存放产生的位置 l存放产生的数量 N一共有多少位置可以选择
int calculate(int k, int * x, int *S, int * l, int N)
{
    int i, j;
    int flag;
    *l = 0;
    int cannot[13] = {0};  //分开两个循环的关键 用变量记录下不可用的数字
    for(j = 0; j <= k - 1; j++)
    {
        cannot[x[j] - 1] = 1;  //不能同一列
        if(x[j] + k - j - 1 <= N - 1) //不能对角线 不能越界
        {
            cannot[x[j] + k - j - 1] = 1;
        }
        if(x[j] - k + j - 1 >= 0)
        {
            cannot[x[j] - k + j - 1] = 1;
        }
    }
    for(i = N; i >= 1; i--) //大数在前面
    {
        if(cannot[i - 1] == 0)
        {
            S[*l] = i;
            (*l)++;
        }
    }
    return 0;
}

int BackTrack(int N, int **ans, int * anum)
{
    *anum = 0;
    int i, j, k;
    int x[13];
    int S[13][13] = {0};
    int l[13] = {0};
    for(i = N - 1; i >= 0;  i--) //大数放前面
    {
        S[0][i] = N - i;
    }
    l[0] = N;
    k = 0;
    do{
        while(l[k] != 0)
        {
            x[k] = S[k][l[k] - 1]; //取最小的
            l[k]--;
            if(k < N - 1)
            {
                k++;
                calculate(k, x, S[k], &l[k], N);
            }
            else
            {
                for(i = 0; i < N; i++)
                {
                    ans[*anum][i] = x[i];
                }
                (*anum)++;
            }
        }
        k--;
    }while(k != -1);
    return 0;
}

int main()
{
    FILE *in, *out;
    in = fopen("checker.in", "r");
    out = fopen("checker.out", "w");

    int N;
    int ** ans;
    int i, j;
    ans = (int **)malloc(100000 * sizeof(int *)); //大内存要自己分配
    for(i = 0; i < 100000; i++)
    {
        ans[i] = (int *)malloc(13 * sizeof(int));
    }
    int anum;
    fscanf(in, "%d", &N);
    BackTrack(N, ans, &anum);


    for(i = 0; i <= 2; i++)
    {
        for(j = 0; j < N - 1; j++)
        {
            fprintf(out, "%d ", ans[i][j]);
        }
        fprintf(out, "%d\n", ans[i][N - 1]);
    }
    fprintf(out, "%d\n", anum);
    return 0;
}

 


联系
我们