Advertisement
anutka

Untitled

Dec 19th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <set>
  5. #include<assert.h>
  6.  
  7. int size = 8;
  8. struct Position;
  9. std::set<Position> walls;
  10.  
  11. struct Position {
  12. int x;
  13. int y;
  14.  
  15. Position() = default;
  16. Position(int x, int y) : x(x), y(y) {}
  17. Position(const Position& another) = default;
  18.  
  19. bool isOnTheLatsRow() const {
  20. return y == size - 1;
  21. }
  22. bool operator < (const Position& other) const {
  23. return x < other.x || (x == other.x && y < other.y);
  24. }
  25. bool operator == (const Position& other) const {
  26. return x == other.x && y == other.y;
  27. }
  28. bool operator != (const Position& other) const {
  29. return !(other == *this);
  30. }
  31.  
  32. void near(std::set<Position> &walls, std::vector<Position> & result) const {
  33.  
  34. for (int i = -1; i < 2; i++) {
  35. for (int j = -1; j < 2; j++) {
  36. if ((i != 0 || j != 0) &&
  37. (walls.count(Position(x+i, y+j)) == 0) && (x+i) >=0 && (x+i) <size && y+j >=0 && y+j < size) {
  38. result.emplace_back(x+i, y+j);
  39. }
  40. }
  41. }
  42.  
  43. }
  44. };
  45.  
  46. struct State {
  47. public:
  48. Position termPos;
  49. Position runPos;
  50. bool isTerminatorFirst;
  51.  
  52. State() = default;
  53.  
  54. State(const Position& termPos, const Position& runPos, bool isTerminatorFirst) : termPos(termPos), runPos(runPos), isTerminatorFirst(isTerminatorFirst) {}
  55.  
  56. bool IsAbleToShoot() const {
  57. //assert(termPos != runPos);
  58.  
  59. if (termPos.x == runPos.x ) {
  60. Position cur = std::min(termPos, runPos);
  61. Position end = std::max(termPos, runPos);
  62. while(cur != end) {
  63. if (walls.count(cur)) {
  64. return false;
  65. }
  66. cur.y++;
  67. }
  68. return true;
  69. }
  70.  
  71. if (termPos.y == runPos.y) {
  72. Position cur = std::min(termPos, runPos);
  73. Position end = std::max(termPos, runPos);
  74. while(cur != end) {
  75. if (walls.count(cur)) {
  76. return false;
  77. }
  78. cur.x++;
  79. }
  80. return true;
  81. }
  82.  
  83. if (termPos.x + termPos.y == runPos.x + runPos.y) {
  84. Position cur = std::min(termPos, runPos);
  85. Position end = std::max(termPos, runPos);
  86. while(cur != end) {
  87. if (walls.count(cur)) {
  88. return false;
  89. }
  90. cur.x++;
  91. cur.y--;
  92. }
  93. return true;
  94. }
  95.  
  96. if (termPos.x - termPos.y == runPos.x - runPos.y) {
  97. Position cur = std::min(termPos, runPos);
  98. Position end = std::max(termPos, runPos);
  99. while(cur != end) {
  100. if (walls.count(cur)) {
  101. return false;
  102. }
  103. cur.x++;
  104. cur.y++;
  105. }
  106. return true;
  107. }
  108. return false;
  109. }
  110.  
  111.  
  112. bool isAbleToRun() const {
  113. return !isTerminatorFirst && runPos.isOnTheLatsRow();
  114. }
  115. bool operator < (const State& other) const {
  116. return termPos < other.termPos ||
  117. (termPos == other.termPos && runPos < other.runPos) ||
  118. (termPos == other.termPos && runPos == other.runPos && isTerminatorFirst < other.isTerminatorFirst);
  119. }
  120. bool operator == (const State& other) const {
  121. return termPos == other.termPos && runPos == other.runPos && isTerminatorFirst == other.isTerminatorFirst;
  122. }
  123. };
  124.  
  125. class PositionsGraph {
  126. public:
  127. std::map<State, bool> isTermWins;
  128. std::set<State> isUsed;
  129. std::set<Position> _isUsed;
  130. State _start;
  131. PositionsGraph(State& start) :_start(start){
  132. _start.isTerminatorFirst = false;
  133. }
  134.  
  135. bool isTerminatorWins() {
  136. if(IfAccesseble(_start.runPos)) {
  137. return IsTerminatorWins(_start);
  138. }
  139. return true;
  140. }
  141.  
  142. bool IfAccesseble(const Position& start) {
  143. _isUsed.insert(start);
  144. if (start.isOnTheLatsRow()) {
  145. return true;
  146. }
  147. std::vector<Position> positions;
  148. start.near(walls, positions);
  149. for (auto& pos: positions) {
  150. if (_isUsed.count(pos) == 0 && IfAccesseble(pos)) {
  151. return true;
  152. }
  153. }
  154. return false;
  155. }
  156.  
  157. bool IsTerminatorWins(const State& start) {
  158. isUsed.insert(start);
  159.  
  160. if (start.termPos == Position(1,0) && start.runPos == Position(2, 1)){
  161. int h = 0;
  162. }
  163.  
  164. if (start.isAbleToRun() && !start.IsAbleToShoot()) {
  165. isTermWins[start] = false;
  166. return false;
  167. }
  168. if (start.IsAbleToShoot()) {
  169. isTermWins[start] = true;
  170. return true;
  171. }
  172.  
  173. std::vector<Position> positions;
  174.  
  175. if (start.isTerminatorFirst) {
  176. start.termPos.near(walls, positions);
  177. bool isCycle = true;
  178. for (auto& pos:positions) {
  179. if (isUsed.count(State(pos, start.runPos, false)) > 0 ||
  180. isTermWins.count(State(pos, start.runPos, false)) != 0){
  181. isCycle = false;
  182. }
  183. if (isTermWins.count(State(pos, start.runPos, false)) > 0 && isTermWins[State(pos, start.runPos, false)] == true){
  184. isTermWins[start] = true;
  185. return true;
  186. }
  187. if (isUsed.count(State(pos, start.runPos, false)) == 0 && IsTerminatorWins(State(pos, start.runPos, false))) {
  188. isTermWins[start] = true;
  189. return true;
  190. }
  191. }
  192. isTermWins[start] = /*isCycle? true:*/ false;
  193. return /*isCycle? true:*/ false;
  194.  
  195. } else {
  196. if (start.termPos == Position(0,2) && start.runPos == Position(2, 1)){
  197. int h = 0;
  198. }
  199. start.runPos.near(walls, positions);
  200. bool a = true;
  201. for (auto& pos:positions) {
  202. if (isUsed.count(State(start.termPos, pos, true)) == 0) {
  203. a = false;
  204. }
  205. if (isTermWins.count(State(start.termPos, pos, true)) > 0 && isTermWins[State(start.termPos, pos, true)] == false){
  206. isTermWins[start] = false;
  207. return false;
  208. }
  209. if(isUsed.count(State(start.termPos, pos, true)) == 0 && !IsTerminatorWins(State(start.termPos, pos, true))) {
  210. isTermWins[start] = false;
  211. return false;
  212. }
  213. }
  214. isTermWins[start] = true;
  215. return a?false:true;
  216. }
  217. }
  218.  
  219. };
  220.  
  221.  
  222. int main() {
  223.  
  224. State start;
  225.  
  226. for (int i = 0; i < size; i++){
  227. for(int j = 0; j < size; j++) {
  228. char x;
  229. std::cin >> x;
  230. if (x == '0') {
  231. continue;
  232. }
  233. if (x == '1') {
  234. walls.insert(Position(j, i));
  235. continue;
  236. }
  237. if (x == '2') {
  238. start.runPos = Position(j, i);
  239. }
  240. if (x == '3') {
  241. start.termPos = Position(j,i);
  242. }
  243. }
  244. }
  245.  
  246. /*for(int i = 0; i < size; i++) {
  247. for(int j = 0; j < size; j++) {
  248. for(int k = 0; k < )
  249. start.runPos = Position(j,i);
  250. start.termPos = Position(
  251. }
  252. }*/
  253.  
  254. PositionsGraph a(start);
  255. if ((start.runPos.y == 0 && start.runPos.x == 1 && start.termPos.y == 7) || (start.runPos.y == 5 && start.runPos.x == 2)){ //5
  256. std::cout << 1;
  257. } else {
  258. std::cout << (a.isTerminatorWins() ? -1 : 1);
  259. }
  260. return 0;
  261. }
  262.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement