#include "osalib.h" #include <vector> #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> char **b; int nn; int mm; using namespace std; class Point { private: int x; int y; public: Point(int _x, int _y) { this->x = _x; this->y = _y; } int getX(){ return this->x; } int getY(){ return this->y; } }; bool isInPoints(vector<Point> points, int x, int y) { for(int i = 0; i < points.size(); i++) { Point p = points[i]; if(x == p.getX() && y == p.getY()) { return true; } } return false; } void findPath(vector<Point> visited, vector<Point> &found, unsigned long long int count, int x, int y) { if(count == found.size()) { return; } if(b[x][y] == 'K' && !isInPoints(found, x, y)) { found.push_back(Point(x, y)); if(count == found.size()) { return; } } visited.push_back(Point(x, y)); if(x+1 < nn && b[x+1][y] != 'W' && !isInPoints(visited, x+1, y)) findPath(visited, found, count, x+1, y); if(x-1 >= 0 && b[x-1][y] != 'W' && !isInPoints(visited, x-1, y)) findPath(visited, found, count, x-1, y); if(y+1 < mm && b[x][y+1] != 'W' && !isInPoints(visited, x, y+1)) findPath(visited, found, count, x, y+1); if(y-1 >= 0 && b[x][y-1] != 'W' && !isInPoints(visited, x, y-1)) findPath(visited, found, count, x, y-1); } void NowaWyspa(int n, int m, char **Board) { nn = n; mm = m; b = (char**)malloc(n * m * sizeof(char*)); memcpy(b, Board, sizeof (char*) * n * m); } int NowaWarownia(int r, int c) { b[r-1][c-1] = 'W'; vector<Point> visited; vector<Point> found; int i = 0; int j = 0; int x = 0; int y = 0; unsigned long long int count = 0; for(i = 0 ; i < nn; i++) { for(j = 0 ; j < mm; j++) { if(b[i][j] == 'K') { count++; x = i; y = j; } } } findPath(visited, found, count, x, y); if(found.size() == count) { return 1; } b[r-1][c-1] = '.'; return 0; } void PrzeniesOsade(int r1, int c1, int r2, int c2) { b[r1-1][c1-1] = '.'; b[r2-1][c2-1] = 'K'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #include "osalib.h" #include <vector> #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> char **b; int nn; int mm; using namespace std; class Point { private: int x; int y; public: Point(int _x, int _y) { this->x = _x; this->y = _y; } int getX(){ return this->x; } int getY(){ return this->y; } }; bool isInPoints(vector<Point> points, int x, int y) { for(int i = 0; i < points.size(); i++) { Point p = points[i]; if(x == p.getX() && y == p.getY()) { return true; } } return false; } void findPath(vector<Point> visited, vector<Point> &found, unsigned long long int count, int x, int y) { if(count == found.size()) { return; } if(b[x][y] == 'K' && !isInPoints(found, x, y)) { found.push_back(Point(x, y)); if(count == found.size()) { return; } } visited.push_back(Point(x, y)); if(x+1 < nn && b[x+1][y] != 'W' && !isInPoints(visited, x+1, y)) findPath(visited, found, count, x+1, y); if(x-1 >= 0 && b[x-1][y] != 'W' && !isInPoints(visited, x-1, y)) findPath(visited, found, count, x-1, y); if(y+1 < mm && b[x][y+1] != 'W' && !isInPoints(visited, x, y+1)) findPath(visited, found, count, x, y+1); if(y-1 >= 0 && b[x][y-1] != 'W' && !isInPoints(visited, x, y-1)) findPath(visited, found, count, x, y-1); } void NowaWyspa(int n, int m, char **Board) { nn = n; mm = m; b = (char**)malloc(n * m * sizeof(char*)); memcpy(b, Board, sizeof (char*) * n * m); } int NowaWarownia(int r, int c) { b[r-1][c-1] = 'W'; vector<Point> visited; vector<Point> found; int i = 0; int j = 0; int x = 0; int y = 0; unsigned long long int count = 0; for(i = 0 ; i < nn; i++) { for(j = 0 ; j < mm; j++) { if(b[i][j] == 'K') { count++; x = i; y = j; } } } findPath(visited, found, count, x, y); if(found.size() == count) { return 1; } b[r-1][c-1] = '.'; return 0; } void PrzeniesOsade(int r1, int c1, int r2, int c2) { b[r1-1][c1-1] = '.'; b[r2-1][c2-1] = 'K'; } |