女皇挑战赛
女皇挑战赛
提问于 2017-02-03 18:24:36
我正在用我用C++写的N皇后代码做一个详尽的搜索。如何进一步优化这段代码？
它接受一个输入n (皇后的数量)，并返回一个具有所有可能安排的vector<vector<string>>。看一下代码，我认为像pop_back()这样的操作正在减慢整个运行时。
#include "stdafx.h"
#include "string"
#include "vector"
using namespace std;
//Struct to store previously placed queens.
struct rowCol {
int row;
int col;
rowCol(int r, int c) {
row = r;
col = c;
}
};
class Solution {
public:
bool check(int row, int col, vector<rowCol*>& history) {
//check diagonals
for (auto i : history) {
if (abs(i->row - row) == abs(i->col - col))
return 0;
}
//check columns
for (auto i : history) {
if (i->col == col)
return 0;
}
return 1;
}
void recurse(vector<rowCol*>& history, int row, int n,vector<string>& res,vector<vector<string>>& result) {
if (row < n) {
for (int j = 0; j < n; j++) {
if (check(row, j, history)) {
std::string x(n, '.');
history.push_back(new rowCol(row, j));
x[j] = 'Q';
res.push_back(x);
if (res.size() == n) {
result.push_back(res);
}
recurse(history, row+1, n, res,result);
res.pop_back();
history.pop_back();
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<rowCol*> history;
vector<string> res;
recurse(history, 0, n,res,result);
return result;
}
};
int main()
{
Solution s;
s.solveNQueens(4);
return 0;
}回答 3
Code Review用户
回答已采纳
发布于 2017-02-03 20:31:29
只在完成
时才构造板字符串
目前，您正在构造一串字符串来表示板的行，但是当板的工作不正确时，就会丢弃它们。如果只在到达解决方案时才构建完整的板，则可以节省时间，因为没有为不正确的板构造所有字符串。下面是我对您的程序进行的修改，使您的程序运行速度提高了2倍：
void recurse(vector<rowCol*>& history, int row, int n,vector<vector<string>>& result) {
if (row < n) {
for (int j = 0; j < n; j++) {
if (check(row, j, history)) {
history.push_back(new rowCol(row, j));
if (row == n-1) {
// Got a solution. Construct the whole board.
vector<string> res(n);
std::string x(n, '.');
for (int k = 0; k < n; k++) {
x[history[k]->col] = 'Q';
res[k] = x;
x[history[k]->col] = '.';
}
result.push_back(res);
}
recurse(history, row+1, n, result);
history.pop_back();
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<rowCol*> history;
recurse(history, 0, n,result);
return result;
}改进rowCol历史
目前，您有一个vector<rowCol *> history，它保存了您所放置的所有以前的皇后。首先要注意的是，history[i]->row总是等于i，因为您一次只放置一排皇后。所以你真的不需要一个rowCol，只需要一个col，它可以是一个简单的int。
需要注意的第二件事是，您的代码花费了大量的时间推送和弹出到history。而不是这样，您只需让history成为大小n的向量，只需跟踪您在其中存储了多少个皇后(也就是rows)。
下面是我如何重写您的程序，它现在比原来的运行速度快了4倍：
class Solution {
public:
bool check(int row, int col, vector<int>& history)
{
for (int i = 0; i < row; i++) {
int col2 = history[i];
if (col2 == col || row - i == abs(col2 - col))
return 0;
}
return 1;
}
void recurse(vector<int>& history, int row, int n,
vector<vector<string>>& result)
{
for (int col = 0; col < n; col++) {
if (check(row, col, history)) {
history[row] = col;
if (row == n-1) {
// Solved it. Create a board and store it.
vector<string> res(n);
std::string x(n, '.');
for (int i = 0; i < n; i++) {
x[history[i]] = 'Q';
res[i] = x;
x[history[i]] = '.';
}
result.push_back(res);
} else {
// Go on to the next row.
recurse(history, row+1, n, result);
}
}
}
}
vector<vector<string>> solveNQueens(int n)
{
vector<vector<string>> result;
vector<int> history(n);
recurse(history, 0, n, result);
return result;
}
};Code Review用户
发布于 2017-02-03 18:54:41
我会让history成为一个vector<rowCol>，而不是使用指针。您正在为一个小结构(一个缓慢的操作)分配内存，而不是释放它，所以它会泄漏。
我认为像pop_back()这样的操作正在减慢整个运行时。
别想了，量一下。pop_back是一种快速操作，因为没有进行内存调用。push_back通常也是快速的，但是当它需要增加存储空间时，可能会花费更长的时间。在您的情况下，这将只发生一次，因为向量被重用，并且分配的空间永远不会缩小。
传递给recurse的大部分内容可以作为Solution类的成员存储，而不是一直以参数的形式传递。
Code Review用户
发布于 2017-02-04 09:25:33
与@jS1的答复相比略有改进。
- 我会把
Solution重命名为Solver。 - 我会在
Solution中使用以下内容。使用溶液= std::vector； - 我会将
std::vector<Solution>用于所有的解决方案。 - 我会简化构建一个解决方案的行。
下面是一个包含这些更改的程序：
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
using Solution = std::vector<std::string>;
class Solver {
public:
bool check(int row, int col, vector<int>& history)
{
for (int i = 0; i < row; i++) {
int col2 = history[i];
if (col2 == col || row - i == abs(col2 - col))
return 0;
}
return 1;
}
void recurse(vector<int>& history, int row, int n,
std::vector<Solution>& solutions)
{
for (int col = 0; col < n; col++) {
if (check(row, col, history)) {
history[row] = col;
if (row == n-1) {
// Solved it. Create the board.
Solution solution(n, std::string(n, '.'));
for (int i = 0; i < n; i++) {
solution[i][history[i]] = 'Q';
}
solutions.push_back(solution);
} else {
// Go on to the next row.
recurse(history, row+1, n, solutions);
}
}
}
}
vector<Solution> solveNQueens(int n)
{
vector<Solution> solutions;
vector<int> history(n);
recurse(history, 0, n, solutions);
return solutions;
}
};
int main(int argc, char** argv)
{
Solver s;
auto res = s.solveNQueens(std::atoi(argv[1]));
for ( auto& solution : res )
{
std::cout << "-- Solution --" << std::endl;
for ( auto& line : solution )
{
std::cout << line << std::endl;
}
}
return 0;
}页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/154380
复制相关文章
相似问题
腾讯云开发者
