Cercavo di risolvere la sfida proposta a metà di questa pagina.
In sostanza dato un singolo input N, bisogna creare una scacchiera NxN e scoprire se è possibile piazzarci sopra N Regine in maniera tale che nessuna di loro minacci un'altra.
Al solito temo di aver complicato la mia soluzione piu del dovuto, tuttavia dà la risposta corretta e passa tutti i testcase, solo che al di sopra di un input quale 7, comincia a diventare troppo lento, temo che la complessità del mio algoritmo sia O(n^n).
Mi domandavo, c'è un modo migliore per completare la sfida che permetta anche di gestire input piu grandi di 7 in tempi ragionevoli? :S
In sostanza dato un singolo input N, bisogna creare una scacchiera NxN e scoprire se è possibile piazzarci sopra N Regine in maniera tale che nessuna di loro minacci un'altra.
Al solito temo di aver complicato la mia soluzione piu del dovuto, tuttavia dà la risposta corretta e passa tutti i testcase, solo che al di sopra di un input quale 7, comincia a diventare troppo lento, temo che la complessità del mio algoritmo sia O(n^n).
Mi domandavo, c'è un modo migliore per completare la sfida che permetta anche di gestire input piu grandi di 7 in tempi ragionevoli? :S
C++:
#include <iostream>
#include <vector>
using namespace std;
struct pos {
int x;
int y;
};
class Board {
public:
Board(int n) :board(n, vector<int>(n, 0)), gridSize{ n } {}
Board& operator=(const Board& rhs);
//methods
void addQueen(int x, int y);
bool isSolved() { return queens.size() == gridSize; }
void printQueens();
//variables
vector<vector<int>> board;
vector<pos> queens;
int gridSize;
private:
void updateOccupied();
};
Board placeQueens(Board);
int main()
{
int N{};
cin >> N;
Board state(N);
state = placeQueens(state);
if (state.queens.size() == N)
{
cout << "YES" << endl;
state.printQueens();
}
else
{
cout << "NO" << endl;
}
return 0;
}
Board placeQueens(Board current)
{
// starts the outer for loop from the row of the last queen placed onward
int y = (current.queens.empty())? 0 : current.queens.back().y;
Board temp(current.gridSize);
for (int i = y; i < current.board.size(); i++)
{
for (int j = 0; j < current.board[0].size(); j++)
{
if (current.board[i][j] == 0)
{
temp = current;
temp.addQueen(j, i);
//base case 1 the first time an answer is found
if (temp.isSolved()) {return temp;}
//recursion
temp = placeQueens(temp);
//base case 2 to propagate up the correct answer
if (temp.isSolved()) { return temp; }
}
}
}
return current;
}
void Board::addQueen(int x, int y)
{
queens.push_back(pos{ x, y });
this->updateOccupied();
}
void Board::updateOccupied()
{
pos& p = queens.back();
//horizontal
board[p.y] = vector<int>(gridSize, 1);
//vertical
for (int i = 0; i < gridSize; i++) { board[i][p.x] = 1; }
//diagonal
bool toggle = true;
int xSign = -1, ySign = -1;
for (int i = 0; i < 4; i++)
{
int x = p.x;
int y = p.y;
while (
x + xSign >= 0 && x + xSign < gridSize &&
y + ySign >= 0 && y + ySign < gridSize
)
{
x += xSign;
y += ySign;
board[y][x] = 1;
}
xSign = toggle ? xSign * -1 : xSign;
ySign = toggle ? ySign : ySign * -1;
toggle = !toggle;
}
}
void Board::printQueens()
{
Board temp(gridSize);
for (auto& q : queens) {
temp.board[q.y][q.x] = 1;
}
for (int i = 0; i < temp.gridSize; i++)
{
for (int j = 0; j < temp.gridSize; j++)
{
cout << temp.board[i][j];
if (j != temp.gridSize - 1) {
cout << " ";
}
}
cout << endl;
}
}
Board& Board::operator=(const Board& rhs)
{
board = rhs.board;
queens = rhs.queens;
gridSize = rhs.gridSize;
return *this;
}
Ultima modifica:
