Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- #include<fstream>
- using namespace std;
- #define MAX_SIZE 8
- bool board[MAX_SIZE][MAX_SIZE] = { false };
- void printBoard(int size, ostream &out)
- {
- out << "+++++++++++++++++++\n";
- for (int r = 0; r < size; r++)
- {
- for (int c = 0; c < size; c++)
- {
- if (board[r][c])
- out << "H ";
- else
- out << "_ ";
- }
- out << endl;
- }
- out << "+++++++++++++++++++ \n";
- }
- #define OPER_PLACE_HORSE 0
- #define OPER_REMOVE_HORSE 1
- #define OPER_FIND_SOLUTION 2
- struct Operation
- {
- int operType;
- int k;
- int size;
- int r;
- int c;
- Operation(int _t, int _k, int _s) :operType(_t), k(_k), size(_s) {}
- Operation(int _t, int _k, int _s, int _r, int _c)
- :operType(_t), k(_k), size(_s), r(_r), c(_c) {}
- //Operation (){}
- };
- bool hasHorse(int r, int c, int size)
- {
- return r >= 0 &&
- c >= 0 &&
- r < size &&
- c < size &&
- board[r][c];
- }
- bool canPlaceHorse(int r, int c, int size)
- {
- return !hasHorse(r - 2, c - 1, size) &&
- !hasHorse(r - 2, c + 1, size) &&
- !hasHorse(r - 1, c - 2, size) &&
- !hasHorse(r - 1, c + 2, size) &&
- !hasHorse(r + 1, c - 2, size) &&
- !hasHorse(r + 1, c + 2, size) &&
- !hasHorse(r + 2, c - 1, size) &&
- !hasHorse(r + 2, c + 1, size) &&
- !hasHorse(r, c, size);
- }
- void configStack(int k, int size, ostream &out)
- {
- stack<Operation> operations;
- operations.push(Operation(OPER_FIND_SOLUTION, k, size));
- while (!operations.empty())
- {
- Operation topOperation = operations.top();
- int k = topOperation.k;
- int size = topOperation.size;
- operations.pop();
- if (k == 0)
- {
- printBoard(size, out);
- }
- else if (topOperation.operType == OPER_PLACE_HORSE)
- {
- board[topOperation.r][topOperation.c] = true;
- }
- else if (topOperation.operType == OPER_REMOVE_HORSE)
- {
- board[topOperation.r][topOperation.c] = false;
- }
- else
- {
- for (int r = 0; r < size; r++)
- {
- for (int c = 0; c < size; c++)
- {
- if (canPlaceHorse(r, c, size))
- {
- operations.push(Operation(OPER_REMOVE_HORSE, 1, size, r, c));
- operations.push(Operation(OPER_FIND_SOLUTION, k - 1, size));
- operations.push(Operation(OPER_PLACE_HORSE, 1, size, r, c));
- }
- }
- }
- }
- }
- }
- void config(int k, int size, ostream&out)
- {
- if (k == 0)
- {
- printBoard(size, out);
- return;
- }
- for (int r = 0; r < size; r++)
- {
- for (int c = 0; c < size; c++)
- {
- if (canPlaceHorse(r, c, size))
- {
- board[r][c] = true;
- config(k - 1, size, out);
- board[r][c] = false;
- }
- }
- }
- }
- int main()
- {
- //makeConfig(cout, 4, 0, 0, 0, 3);
- //makeConfig(cout, 4, 0, 3, 3, 3);
- //makeConfig(cout, 4, 1, 1, 1, 3);
- /*ofstream out;
- out.open("data2.txt");
- configStack(2, 4, out);
- out.close();
- ofstream out;
- out.open("data3.txt");
- config(2, 4, out);
- out.close();*/
- /*ofstream out;
- out.open("3x3table.txt");
- configStack(2, 3, out);
- out.close();*/
- }
- class:
- #include <iostream>
- #include <stack>
- #include<fstream>
- #include<assert.h>
- using namespace std;
- #include <iostream>
- #include<iomanip>
- #include <stack>
- using namespace std;
- #define MAX_SIZE 8
- bool board[MAX_SIZE][MAX_SIZE] = { false };
- #define OPER_PLACE_HORSE 0
- #define OPER_REMOVE_HORSE 1
- #define OPER_FIND_SOLUTION 2
- struct Operation {
- int operType;
- int k;
- int size;
- int r;
- int c;
- Operation(int _t, int _k, int _s) :operType(_t), k(_k), size(_s) {}//k is the number of horses
- Operation(int _t, int _k, int _s, int _r, int _c)
- :operType(_t), k(_k), size(_s), r(_r), c(_c) {}
- };
- class HorseConfig {
- private:
- int k;
- int size;
- public:
- HorseConfig(int kk, int s) :k(kk), size(s) {}
- void printBoard()
- {
- cout << "+++++++++++++++++++\n";
- for (int r = 0; r < size; r++)
- {
- for (int c = 0; c < size; c++)
- {
- if (board[r][c])
- cout << "H ";
- else
- cout << "_ ";
- }
- cout << endl;
- }
- cout << "+++++++++++++++++++\n";
- }
- bool hasHorse(int r, int c)
- {
- return r >= 0 &&
- c >= 0 &&
- r < size &&
- c < size &&
- board[r][c];//da ni e true t.e da ima neshto na board-a
- }
- bool canPlaceHorse(int r, int c)
- {
- return !hasHorse(r - 2, c - 1) &&
- !hasHorse(r - 2, c + 1) &&
- !hasHorse(r - 1, c - 2) &&
- !hasHorse(r - 1, c + 2) &&
- !hasHorse(r + 1, c - 2) &&
- !hasHorse(r + 1, c + 2) &&
- !hasHorse(r + 2, c - 1) &&
- !hasHorse(r + 2, c + 1) &&
- !hasHorse(r, c);
- }
- void configStack()
- {
- stack<Operation> operations;
- operations.push(Operation(OPER_FIND_SOLUTION, k, size));
- while (!operations.empty())
- {
- Operation topOperation = operations.top();
- int k = topOperation.k;//tezi k i size koito sme podali
- //int size = topOperation.size;
- operations.pop();
- if (k == 0)//if there aren't any horses
- {
- printBoard();
- }
- else if (topOperation.operType == OPER_PLACE_HORSE)
- {
- board[topOperation.r][topOperation.c] = true;
- }
- else if (topOperation.operType == OPER_REMOVE_HORSE)
- {
- board[topOperation.r][topOperation.c] = false;
- }
- else//if it is find solution
- {
- for (size_t r = 0; r < size; r++)
- {
- for (size_t c = 0; c < size; c++)
- {
- if (canPlaceHorse(r, c))
- {
- operations.push(Operation(OPER_REMOVE_HORSE, 1, size, r, c));
- operations.push(Operation(OPER_FIND_SOLUTION, k - 1, size));
- operations.push(Operation(OPER_PLACE_HORSE, 1, size, r, c));
- }
- }
- }
- }
- }
- }
- void nextConfig(int r1, int c1, int r2, int c2)
- {
- assert(r1 != r2&&c1 != 2);
- board[r1][c1] = true;
- board[r2][c2] = true;
- if (c2 + 1 < size)
- {
- board[r2][c2] = false;
- board[r2][c2 + 1] = true;
- }
- else if (r2 + 1<size)
- {
- board[r2][c2] = false;
- board[r2 + 1][0] = true;
- }
- else if (c1 + 1<size)
- {
- board[r1][c1] = false;
- board[r2][c2] = false;
- board[r1][c1 + 1] = true;
- board[0][0] = true;
- }
- else if (r1 + 1<size)//ako e na 3ta kolona
- {
- board[r1][c1] = false;
- board[r2][c2] = false;
- board[r1 + 1][0] = true;
- board[0][0] = true;
- }
- printBoard();
- board[MAX_SIZE][MAX_SIZE] = { false };
- }
- bool noMoreConfigs(int r1, int c1,int r2,int c2, int size)
- {
- if (r1+1 >= size&&c1+1>=size&&r2+1>=size&&c2+2>=size)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
- };
- int main()
- {
- HorseConfig a(2, 4);
- //a.configStack();
- //a.nextConfig(0, 0, 0, 3);//no ne 2 ednovremenno
- //a.nextConfig(2, 1, 2, 2);
- //a.nextConfig(1, 1, 1, 3);
- //a.nextConfig(1, 1, 3, 3);
- a.nextConfig(1, 3, 3, 3);
- //a.nextConfig(1, 3, 1, 3);//dava assertion failure kakto iskame
- cout << a.noMoreConfigs(1, 1, 1, 3, 4) << endl;
- cout << a.noMoreConfigs(3, 3, 3, 2, 4) << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment