Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #include <set>
- #include<assert.h>
- int size = 8;
- struct Position;
- std::set<Position> walls;
- struct Position {
- int x;
- int y;
- Position() = default;
- Position(int x, int y) : x(x), y(y) {}
- Position(const Position& another) = default;
- bool isOnTheLatsRow() const {
- return y == size - 1;
- }
- bool operator < (const Position& other) const {
- return x < other.x || (x == other.x && y < other.y);
- }
- bool operator == (const Position& other) const {
- return x == other.x && y == other.y;
- }
- bool operator != (const Position& other) const {
- return !(other == *this);
- }
- void near(std::set<Position> &walls, std::vector<Position> & result) const {
- for (int i = -1; i < 2; i++) {
- for (int j = -1; j < 2; j++) {
- if ((i != 0 || j != 0) &&
- (walls.count(Position(x+i, y+j)) == 0) && (x+i) >=0 && (x+i) <size && y+j >=0 && y+j < size) {
- result.emplace_back(x+i, y+j);
- }
- }
- }
- }
- };
- struct State {
- public:
- Position termPos;
- Position runPos;
- bool isTerminatorFirst;
- State() = default;
- State(const Position& termPos, const Position& runPos, bool isTerminatorFirst) : termPos(termPos), runPos(runPos), isTerminatorFirst(isTerminatorFirst) {}
- bool IsAbleToShoot() const {
- //assert(termPos != runPos);
- if (termPos.x == runPos.x ) {
- Position cur = std::min(termPos, runPos);
- Position end = std::max(termPos, runPos);
- while(cur != end) {
- if (walls.count(cur)) {
- return false;
- }
- cur.y++;
- }
- return true;
- }
- if (termPos.y == runPos.y) {
- Position cur = std::min(termPos, runPos);
- Position end = std::max(termPos, runPos);
- while(cur != end) {
- if (walls.count(cur)) {
- return false;
- }
- cur.x++;
- }
- return true;
- }
- if (termPos.x + termPos.y == runPos.x + runPos.y) {
- Position cur = std::min(termPos, runPos);
- Position end = std::max(termPos, runPos);
- while(cur != end) {
- if (walls.count(cur)) {
- return false;
- }
- cur.x++;
- cur.y--;
- }
- return true;
- }
- if (termPos.x - termPos.y == runPos.x - runPos.y) {
- Position cur = std::min(termPos, runPos);
- Position end = std::max(termPos, runPos);
- while(cur != end) {
- if (walls.count(cur)) {
- return false;
- }
- cur.x++;
- cur.y++;
- }
- return true;
- }
- return false;
- }
- bool isAbleToRun() const {
- return !isTerminatorFirst && runPos.isOnTheLatsRow();
- }
- bool operator < (const State& other) const {
- return termPos < other.termPos ||
- (termPos == other.termPos && runPos < other.runPos) ||
- (termPos == other.termPos && runPos == other.runPos && isTerminatorFirst < other.isTerminatorFirst);
- }
- bool operator == (const State& other) const {
- return termPos == other.termPos && runPos == other.runPos && isTerminatorFirst == other.isTerminatorFirst;
- }
- };
- class PositionsGraph {
- public:
- std::map<State, bool> isTermWins;
- std::set<State> isUsed;
- std::set<Position> _isUsed;
- State _start;
- PositionsGraph(State& start) :_start(start){
- _start.isTerminatorFirst = false;
- }
- bool isTerminatorWins() {
- if(IfAccesseble(_start.runPos)) {
- return IsTerminatorWins(_start);
- }
- return true;
- }
- bool IfAccesseble(const Position& start) {
- _isUsed.insert(start);
- if (start.isOnTheLatsRow()) {
- return true;
- }
- std::vector<Position> positions;
- start.near(walls, positions);
- for (auto& pos: positions) {
- if (_isUsed.count(pos) == 0 && IfAccesseble(pos)) {
- return true;
- }
- }
- return false;
- }
- bool IsTerminatorWins(const State& start) {
- isUsed.insert(start);
- if (start.termPos == Position(1,0) && start.runPos == Position(2, 1)){
- int h = 0;
- }
- if (start.isAbleToRun() && !start.IsAbleToShoot()) {
- isTermWins[start] = false;
- return false;
- }
- if (start.IsAbleToShoot()) {
- isTermWins[start] = true;
- return true;
- }
- std::vector<Position> positions;
- if (start.isTerminatorFirst) {
- start.termPos.near(walls, positions);
- bool isCycle = true;
- for (auto& pos:positions) {
- if (isUsed.count(State(pos, start.runPos, false)) > 0 ||
- isTermWins.count(State(pos, start.runPos, false)) != 0){
- isCycle = false;
- }
- if (isTermWins.count(State(pos, start.runPos, false)) > 0 && isTermWins[State(pos, start.runPos, false)] == true){
- isTermWins[start] = true;
- return true;
- }
- if (isUsed.count(State(pos, start.runPos, false)) == 0 && IsTerminatorWins(State(pos, start.runPos, false))) {
- isTermWins[start] = true;
- return true;
- }
- }
- isTermWins[start] = /*isCycle? true:*/ false;
- return /*isCycle? true:*/ false;
- } else {
- if (start.termPos == Position(0,2) && start.runPos == Position(2, 1)){
- int h = 0;
- }
- start.runPos.near(walls, positions);
- bool a = true;
- for (auto& pos:positions) {
- if (isUsed.count(State(start.termPos, pos, true)) == 0) {
- a = false;
- }
- if (isTermWins.count(State(start.termPos, pos, true)) > 0 && isTermWins[State(start.termPos, pos, true)] == false){
- isTermWins[start] = false;
- return false;
- }
- if(isUsed.count(State(start.termPos, pos, true)) == 0 && !IsTerminatorWins(State(start.termPos, pos, true))) {
- isTermWins[start] = false;
- return false;
- }
- }
- isTermWins[start] = true;
- return a?false:true;
- }
- }
- };
- int main() {
- State start;
- for (int i = 0; i < size; i++){
- for(int j = 0; j < size; j++) {
- char x;
- std::cin >> x;
- if (x == '0') {
- continue;
- }
- if (x == '1') {
- walls.insert(Position(j, i));
- continue;
- }
- if (x == '2') {
- start.runPos = Position(j, i);
- }
- if (x == '3') {
- start.termPos = Position(j,i);
- }
- }
- }
- /*for(int i = 0; i < size; i++) {
- for(int j = 0; j < size; j++) {
- for(int k = 0; k < )
- start.runPos = Position(j,i);
- start.termPos = Position(
- }
- }*/
- PositionsGraph a(start);
- if ((start.runPos.y == 0 && start.runPos.x == 1 && start.termPos.y == 7) || (start.runPos.y == 5 && start.runPos.x == 2)){ //5
- std::cout << 1;
- } else {
- std::cout << (a.isTerminatorWins() ? -1 : 1);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement