正文
【USACO】checker
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
一看题目 经典的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 = ;
for(i = N; i >= ; i--) //大数在前面
{
flag = ;
for(j = ; j <= k - ; j++)
{
if(i == x[j] || i - x[j] == k - j || x[j] - i == k - j )
{
flag = ;
}
}
if(flag == )
{
S[*l] = i;
(*l)++;
}
}
return ;
} int BackTrack(int N, int (*ans)[], int * anum)
{
*anum = ;
int i, j, k;
int x[];
int S[][] = {};
int l[] = {};
for(i = N - ; i >= ; i--) //大数放前面
{
S[][i] = N - i;
}
l[] = N;
k = ;
do{
while(l[k] != )
{
x[k] = S[k][l[k] - ]; //取最小的
l[k]--;
if(k < N - )
{
k++;
calculate(k, x, S[k], &l[k], N);
}
else
{
for(i = ; i < N; i++)
{
ans[*anum][i] = x[i];
}
(*anum)++;
}
}
k--;
}while(k != -);
return ;
} int main()
{
FILE *in, *out;
in = fopen("checker.in", "r");
out = fopen("checker.out", "w"); int N;
int ans[][];
int anum;
fscanf(in, "%d", &N);
BackTrack(N, ans, &anum); int i, j;
for(i = ; i <= ; i++)
{
for(j = ; j < N - ; j++)
{
fprintf(out, "%d ", ans[i][j]);
}
fprintf(out, "%d\n", ans[i][N - ]);
}
fprintf(out, "%d\n", anum);
return ;
}
-------------------------------------
优化了一下计算新一层可能产生的数的算法 把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 = ;
int cannot[] = {}; //分开两个循环的关键 用变量记录下不可用的数字
for(j = ; j <= k - ; j++)
{
cannot[x[j] - ] = ; //不能同一列
if(x[j] + k - j - <= N - ) //不能对角线 不能越界
{
cannot[x[j] + k - j - ] = ;
}
if(x[j] - k + j - >= )
{
cannot[x[j] - k + j - ] = ;
}
}
for(i = N; i >= ; i--) //大数在前面
{
if(cannot[i - ] == )
{
S[*l] = i;
(*l)++;
}
}
return ;
} int BackTrack(int N, int **ans, int * anum)
{
*anum = ;
int i, j, k;
int x[];
int S[][] = {};
int l[] = {};
for(i = N - ; i >= ; i--) //大数放前面
{
S[][i] = N - i;
}
l[] = N;
k = ;
do{
while(l[k] != )
{
x[k] = S[k][l[k] - ]; //取最小的
l[k]--;
if(k < N - )
{
k++;
calculate(k, x, S[k], &l[k], N);
}
else
{
for(i = ; i < N; i++)
{
ans[*anum][i] = x[i];
}
(*anum)++;
}
}
k--;
}while(k != -);
return ;
} 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( * sizeof(int *)); //大内存要自己分配
for(i = ; i < ; i++)
{
ans[i] = (int *)malloc( * sizeof(int));
}
int anum;
fscanf(in, "%d", &N);
BackTrack(N, ans, &anum); for(i = ; i <= ; i++)
{
for(j = ; j < N - ; j++)
{
fprintf(out, "%d ", ans[i][j]);
}
fprintf(out, "%d\n", ans[i][N - ]);
}
fprintf(out, "%d\n", anum);
return ;
}
