Crazy.cpp

#include <iostream>
#include <vector>
#include <string>
#include <tuple>

/*
 * w => y, h => x, row = grow y, map[x][y]
 */

class Robot;
std::ostream &operator<<(std::ostream &os, Robot r);

class Maze{
private:
    const int w, h;
    std::vector<std::string> map;

public:
    Maze(const int w, const int h):w(w),h(h){}
    void insert_row(const std::string &row){
        map.emplace_back(row);
    }
    inline bool check_available(const int x, const int y) const {
        return x >= 0 && x < h && y >= 0 && y < w && map[x][y] != '#';
    }
    std::pair<int, int> findRobot(){
        for(int i = 0 ; i < h ; ++i){ // x
            for(int j = 0 ; j < w ; ++j){ // y
                if(map[i][j] == 'O'){
                    return std::make_pair(i, j);
                }
            }
        }
        return std::make_pair(0, 0);
    }

    friend std::ostream &operator<<(std::ostream &os, Robot r);
};

class Robot{
private:
    int x, y, d=0;
    std::vector<std::tuple<int, int, int>> past;
    const static int movement[][2];

    int is_walked() const {
        for(auto &[xp, yp, dp] : past){
            if(xp == x && yp == y && dp == d) return true;
        }
        return false;
    }

    void rotate(){
        d = (d+1)%4;
    }

    void forward(){
        x += movement[d][0];
        y += movement[d][1];
    }

    std::pair<int, int> futurePosition() const {
        return std::make_pair(x + movement[d][0], y + movement[d][1]);
    }

public:
    Maze maze;
    Robot(const int w, const int h):maze(w, h){}
    void run(const int time){
        for(int i = 0 ; i < time ; ++i){
            std::cerr << x << ' ' << y << ' ' << d << '\n';
            std::cerr << *this << '\n';
            // walk
            if(!is_walked()){
                int fx, fy;
                std::tie(fx, fy) = futurePosition();
                while(!maze.check_available(fx, fy)){
                    rotate();
                    std::tie(fx, fy) = futurePosition();
                }
                past.emplace_back(x, y, d);
                forward();
            }
            else{ // jump loop
                int lp; // loop index
                for(lp = int(past.size()); lp >= 0 ; --lp){
                    auto [_x, _y, _d] = past[lp];
                    if(_x == x && _y == y && _d == d){
                        break;
                    }
                }
                const int loop_size = int(past.size()) - lp;
                const int remain = time - i;
                const int state = (int(past.size() - loop_size)) + (remain % loop_size);
                std::tie(x, y, d) = past[state];
                i = time; // break
            }
        }
    }

    void init(){
        std::tie(x, y) = maze.findRobot();
    }

    const std::pair<int, int> getPosition() const{
        return std::make_pair(x, y);
    }

    friend std::ostream &operator<<(std::ostream &os, Robot r);
};

const int Robot::movement[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

std::ostream &operator<<(std::ostream &os, Robot r){
    for(int i = 0 ; i < int(r.maze.map.size()) ; ++i){
        for(int j = 0 ; j < int(r.maze.map[i].size()) ; ++j){
            if(i == r.x && j == r.y){
                os << 'O';
            }
            else{
                if(r.maze.map[i][j] == 'O'){
                    os << '.';
                }
                else{
                    os << r.maze.map[i][j];
                }
            }
        }
        os << '\n';
    }
    return os;
}


int main(){
    int w, h;
    std:: cin >> w >> h; std::cin.ignore();
    long long n;
    std::cin >> n; std::cin.ignore();

    Robot robot(w, h);

    for (int i = 0; i < h; i++) {
        std::string line;
        getline(std::cin, line);
        robot.maze.insert_row(line);
    }
    robot.init();
    robot.run(n);
    auto [x, y] = robot.getPosition();
    std::cout << y << ' ' << x << '\n';
    std::cerr << robot << '\n';
    return 0;
}