我想修改N-Queens回溯算法,从标准输入中获取板的大小(N),而不是将N定义为常数。 但是,我不能匹配函数处的类型。 我是不是应该定义某种全局最大常数,然后用n来工作?
代码如下:
#include <iostream>
using namespace std;
bool safe(int N, char mat[][N], int v, int k)
{
int i, j;
for (i = 0; i < v; i++)
if (mat[i][k] == 'Q')
return false;
for (i = v, j = k; i >= 0 && j >= 0; i--, j--)
if (mat[i][j] == 'Q')
return false;
for (i = v, j = k; i >= 0 && j < N; i--, j++)
if (mat[i][j] == 'Q')
return false;
return true;
}
void backtrack(int N, char mat[][N], int v)
{
if (v == N)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << mat[i][j] << " ";
cout << endl;
}
cout << endl;
return;
}
for (int i = 0; i < N; i++)
{
if (safe(N, mat, v, i))
{
mat[v][i] = 'Q';
backtrack(N, mat, v + 1);
mat[v][i] = '-';
}
}
}
int main()
{
int N;
cin >> N;
char mat[N][N];
memset(mat, '-', sizeof mat);
backtrack(N,mat, 0);
return 0;
}
charmat[N][N];
是一个可变长度数组(VLA),它是非标准扩展的一些C++编译器,您应该避免使用这些编译器。 如果您需要运行时分配的内存,请考虑使用std::vector
:
int N{};
std::cin >> N;
std::vector<std::vector<char>> mat(N, std::vector<char>(N, '-'));
会做你想做的事。 然后,您可以使用以下方法将其传递给任何函数:
void foo(const std::vector<std::vector<char>>& mat); // for read-only
void foo(std::vector<std::vector<char>>& mat); // for read-write
注意:根据内存的分配方式,这可能会降低效率。 如果你需要你的内存排列在一起,使用一个一维向量和访问函数为你获取索引。