11232: 【原1232】maze

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1232

Description

P332.2&5

Input Format

第一行三个整数 N A B，表示迷宫的大小，也就是一共N行。两个整数A, B，分别表示入口和出口的格子编号。

解释：格子编号就是从上往下横着一行一行的数，分别是1234……

第二行开始不知道有多少行，一行两个整数Pi和Qi。表示第i次砸墙的参数，Pi表示砸的是哪个格子周围的墙,Qi一共有0,1,2,3四种可能性，分别表示砸左上、右上、左下、右下的墙。

为了简化问题，左右的墙就不给砸了，砸墙啥的请参考书上的形容（挺喜感。。。）

Output Format

输出一行一列整数空格隔开，表示从入口到出口的路径

Sample Input

2 2 3
2 1 // 2号格子右上
1 3 // 1号格子右下
2 0
3 0

Sample Output

2 1 3

Tips

按书上第五题的要求，路径压缩的find函数不许用递归！

砸墙如果砸的是最外层的墙的话，是砸不掉的。。。（就当没砸）。

另外，输入有很多很多行，砸到某一行发觉入口和出口通了就直接输出结果，并终止程序。

如果说路径有很多很多很多很多很多的话。。。输出字典序最小的路径。

解释：比如 1 2 4 和 1 3 4 都可以的话就输出前者。

ligongzzz's solution

#include "iostream"
#include "cstring"
using namespace std;

template <class T>
class mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //反向迭代器
    template <class U>
    class reverse_iterator {
        U val;
        friend reverse_iterator<U> mVector<T>::rbegin();
        friend reverse_iterator<U> mVector<T>::rend();
    public:
        U& base() {
            return val;
        }
        reverse_iterator() = default;
        reverse_iterator(const reverse_iterator<U>& other) {
            val = other.val;
        }
        reverse_iterator(const U& other) {
            val = other;
        }
        reverse_iterator<U>& operator++() {
            --val;
            return *this;
        }
        reverse_iterator<U> operator++(int) {
            reverse_iterator<U> temp(*this);
            --val;
            return temp;
        }
        reverse_iterator<U>& operator--() {
            ++val;
            return *this;
        }
        reverse_iterator<U> operator--(int) {
            reverse_iterator<U> temp(*this);
            ++val;
            return temp;
        }
        bool operator==(const reverse_iterator<U>& other) const {
            return val == other.val;
        }
        bool operator!=(const reverse_iterator<U>& other) const {
            return val != other.val;
        }
        reverse_iterator<U>& operator=(const reverse_iterator<U>& other) {
            val = other.val;
            return *this;
        }
        T& operator*() const {
            return *val;
        }
    };

    reverse_iterator<iterator> rbegin() {
        auto temp = end();
        --temp;
        reverse_iterator<iterator> result;
        result.val = temp;
        return result;
    }

    reverse_iterator<iterator> rend() {
        auto temp = begin();
        --temp;
        reverse_iterator<iterator> result;
        result.val = temp;
        return result;
    }

    //增加元素
    void push_back(const T & val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[--size];
        vector_data[size] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //删除
    void erase(const iterator & val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    //重载运算符
    T & operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

    size_t get_size() {
        return size;
    }
};

template <class T>
class mQueue {
    class node {
    public:
        T data;
        node* next = nullptr;
    };
    node* head = nullptr,
        * rear = nullptr;
    size_t _size = 0;

public:
    //构造函数
    mQueue() {
        head = new node;
        rear = head;
    }
    //判断是否为空
    bool empty() {
        return head->next == nullptr;
    }
    //增加
    void push(const T& val) {
        rear->next = new node;
        rear = rear->next;
        rear->data = val;
        ++_size;
    }
    //删除
    void pop() {
        //安全措施
        if (head->next == nullptr)
            return;
        auto temp = head->next;
        delete head;
        head = temp;
        --_size;
    }
    //大小
    size_t size() {
        return _size;
    }
    //最前
    T& front() {
        return head->next->data;
    }
    //最后
    T& back() {
        return rear->data;
    }
    //迭代器
    class iterator {
        node* val = nullptr;
        friend iterator mQueue<T>::begin();
        friend iterator mQueue<T>::end();
    public:
        iterator() = default;
        iterator(const iterator& other) {
            val = other.val;
        }

        iterator& operator++() {
            //安全措施
            if (val == nullptr)
                return *this;
            val = val->next;
            return *this;
        }
        iterator operator++(int) {
            //安全措施
            if (val == nullptr)
                return *this;
            auto temp = *this;
            val = val->next;
            return temp;
        }
        bool operator==(const iterator & other) const {
            return val == other.val;
        }
        bool operator!=(const iterator & other) const {
            return val != other.val;
        }
        T& operator*() {
            return val->data;
        }
    };
    iterator begin() {
        iterator temp;
        temp.val = head->next;
        return temp;
    }
    iterator end() {
        iterator temp;
        temp.val = nullptr;
        return temp;
    }
};

template <class T>
class mSet {
    //颜色枚举类型
    enum colorT { RED, BLACK };

    //结点
    class node {
    public:
        T* data;
        node* lchild = nullptr;
        node* rchild = nullptr;
        node* parent = nullptr;

        colorT color = RED;
    };

    //根节点
    node* root = nullptr;

    //清空
    void clear(node* p) {
        if (p != nullptr) {
            clear(p->lchild);
            clear(p->rchild);
            delete p->data;
            delete p;
        }
        p = nullptr;
    }

    //旋转
    //LL旋转
    void LL(node* gp) {
        auto p = gp->lchild, t = p->lchild;
        if (gp->parent != nullptr) {
            if (gp->parent->lchild == gp)
                gp->parent->lchild = p;
            else
                gp->parent->rchild = p;
        }
        else
            root = p;
        p->parent = gp->parent;
        gp->lchild = p->rchild;
        if (p->rchild != nullptr)
            p->rchild->parent = gp;
        p->rchild = gp;
        gp->parent = p;
        //修改颜色
        auto tmp = gp->color;
        gp->color = p->color;
        p->color = tmp;
        //cout << "LL ";
    }

    //RR旋转
    void RR(node * gp) {
        auto p = gp->rchild, t = p->rchild;
        if (gp->parent != nullptr) {
            if (gp->parent->lchild == gp)
                gp->parent->lchild = p;
            else
                gp->parent->rchild = p;
        }
        else
            root = p;
        p->parent = gp->parent;
        gp->rchild = p->lchild;
        if (p->lchild != nullptr)
            p->lchild->parent = gp;
        p->lchild = gp;
        gp->parent = p;
        //修改颜色
        auto tmp = gp->color;
        gp->color = p->color;
        p->color = tmp;
        //cout << "RR ";
    }

    //LR旋转
    void LR(node * gp) {
        RR(gp->lchild);
        LL(gp);
        //cout << "LR ";
    }

    //RL旋转
    void RL(node * gp) {
        LL(gp->rchild);
        RR(gp);
        //cout << "RL ";
    }

    //插入调整
    void insertAdjust(node * &gp, node * &p, node * t) {
        if (p->color == BLACK) return;
        if (p == root) {
            p->color = BLACK;
            return;
        }
        if (gp->lchild == p) {
            if (p->lchild == t) {
                LL(gp);
                //交换次序
                auto tmp = gp;
                gp = p;
                p = tmp;

            }
            else {
                LR(gp);
                //交换次序
                auto tmp = gp;
                gp = t;
                t = tmp;
            }
        }
        else if (p->rchild == t) {
            RR(gp);
            //交换次序
            auto tmp = gp;
            gp = p;
            p = tmp;
        }
        else {
            RL(gp);
            //交换次序
            auto tmp = gp;
            gp = t;
            t = tmp;
        }
    }

    //删除调整
    void removeAdjust(node * &p, node * &c, node * &t, const T & del) {
        if (c->color == RED) return;
        if (c == root)
            if (c->lchild && c->rchild
                && c->rchild->color == c->lchild->color) {
                c->color = RED;
                c->lchild->color = c->rchild->color = BLACK;
                return;
            }
        if ((c->lchild && c->lchild->color || c->lchild == nullptr) &&
            (c->rchild && c->rchild->color || c->rchild == nullptr))
            if ((t->lchild && t->lchild->color || t->lchild == nullptr) &&
                (t->rchild && t->rchild->color || t->rchild == nullptr)) {
                p->color = BLACK;
                t->color = c->color = RED;
            }
            else {
                if (p->lchild == t)
                    if (t->lchild != nullptr && t->lchild->color == RED) {
                        t->lchild->color = BLACK;
                        LL(p);
                        //交换次序
                        t = p;
                    }
                    else {
                        auto tmp = t->rchild;
                        LR(p);
                        p = tmp;
                        p = p->rchild;
                        p->color = BLACK;
                        t->color = BLACK;
                    }
                else if (t->rchild && t->rchild->color == RED) {
                    t->rchild->color = BLACK;
                    RR(p);
                    t = p;
                }
                else {
                    auto tmp = t->lchild;
                    RL(p);
                    p = tmp;
                    p = p->lchild;
                    p->color = BLACK;
                    t->color = BLACK;
                }
                c->color = RED;
            }
        else {
            if (*c->data == del) {
                if (c->lchild && c->rchild) {
                    if (c->rchild->color == BLACK) {
                        LL(c);
                    }
                    return;
                }
                if (c->lchild) {
                    LL(c);
                    p = c->parent;
                }
                else {
                    RR(c);
                    p = c->parent;
                }
            }
            else {
                p = c;
                c = del < *p->data ? p->lchild : p->rchild;
                t = c == p->lchild ? p->rchild : p->lchild;
                if (c->color == BLACK) {
                    if (t == p->rchild)
                        RR(p);
                    else
                        LL(p);
                    t = p;
                    t = c == p->lchild ? p->rchild : p->lchild;
                    removeAdjust(p, c, t, del);
                }
            }
        }
    }

    //复制
    void copy(node * posDes, node * posSource) {
        posDes->data = new T(*posSource->data);
        posDes->color = posSource->color;
        if (posSource->lchild) {
            posDes->lchild = new node;
            posDes->lchild->parent = posDes;
            copy(posDes->lchild, posSource->lchild);
        }
        if (posSource->rchild) {
            posDes->rchild = new node;
            posDes->rchild->parent = posDes;
            copy(posDes->rchild, posSource->rchild);
        }
    }

public:
    //迭代器
    class iterator {
        node* currentData = nullptr;
        friend iterator mSet::begin();
        friend iterator mSet::find(const T&);
        friend void mSet::erase(const iterator&);

    public:
        iterator() = default;

        iterator(const iterator& b) {
            currentData = new node;
            currentData = b.currentData;
        }

        T& get() {
            return *currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr;
        }

        //重载++i
        iterator& operator++() {
            if (currentData == nullptr)
                return *this;
            //假如有右孩子
            if (currentData->rchild != nullptr) {
                for (currentData = currentData->rchild; currentData->lchild != nullptr;)
                    currentData = currentData->lchild;
            }
            //假如是落单的根节点
            else if (currentData->parent == nullptr) {
                currentData = nullptr;
            }
            //假如是左叶子
            else if (currentData->parent->lchild == currentData)
                currentData = currentData->parent;
            //假如是右叶子
            else {
                auto last = currentData;
                for (currentData = currentData->parent;
                    currentData != nullptr && currentData->rchild == last;
                    currentData = currentData->parent)
                    last = currentData;
            }
            return *this;
        }

        //重载i++
        iterator operator++(int) {
            auto temp = *this;
            if (currentData == nullptr)
                return temp;
            //假如有右孩子
            if (currentData->rchild != nullptr) {
                for (currentData = currentData->rchild; currentData->lchild != nullptr;)
                    currentData = currentData->lchild;
            }
            //假如是落单的根节点
            else if (currentData->parent == nullptr) {
                currentData = nullptr;
            }
            //假如是左叶子
            else if (currentData->parent->lchild == currentData)
                currentData = currentData->parent;
            //假如是右叶子
            else {
                auto last = currentData;
                for (currentData = currentData->parent;
                    currentData != nullptr && currentData->rchild == last;
                    currentData = currentData->parent)
                    last = currentData;
            }
            return temp;
        }

        //重载取值符号
        T& operator*() const {
            if (currentData == nullptr)
                return *new T;
            else
                return *currentData->data;
        }

        //重载==符号
        bool operator==(const iterator & b) const {
            return currentData == b.currentData;
        }

        //重载!=符号
        bool operator!=(const iterator & b) const {
            return currentData != b.currentData;
        }
    };

    //查找
    iterator find(const T & num) {
        iterator ans;
        auto p = root;
        while (p != nullptr && *p->data != num)
            if (*p->data > num)
                p = p->lchild;
            else
                p = p->rchild;

        ans.currentData = p;
        return ans;
    }

    //清空
    void clear() {
        clear(root);
    }

    //插入
    void insert(const T & x) {
        node* t, * parent, * grandp;

        //在空树上插入
        if (root == nullptr) {
            root = new node;
            root->color = BLACK;
            root->data = new T(x);
            return;
        }

        parent = grandp = t = root;
        while (true) {
            if (t != nullptr) {
                if (t->lchild && t->lchild->color == RED &&
                    t->rchild && t->rchild->color == RED) {
                    t->lchild->color = t->rchild->color = BLACK;
                    t->color = RED;
                    insertAdjust(grandp, parent, t);
                }
                grandp = parent;
                parent = t;
                t = *t->data > x ? t->lchild : t->rchild;
            }
            else {
                t = new node;
                t->data = new T(x);
                t->parent = parent;
                if (x < *parent->data)
                    parent->lchild = t;
                else
                    parent->rchild = t;
                insertAdjust(grandp, parent, t);
                root->color = BLACK;
                return;
            }
        }
    }

    //查找删除
    void remove(const T & x) {
        T del = x;
        node* t, * p, * c;

        if (root == nullptr) return;
        if (*root->data == x && root->lchild == nullptr && root->rchild == nullptr) {
            delete root;
            root = nullptr;
            return;
        }

        p = c = t = root;
        while (true) {
            removeAdjust(p, c, t, del);
            if (*c->data == del && c->lchild && c->rchild) {
                auto tmp = c->rchild;
                while (tmp->lchild)
                    tmp = tmp->lchild;
                c->data = tmp->data;
                del = *tmp->data;
                p = c;
                c = c->rchild;
                t = p->lchild;
                continue;
            }

            if (*c->data == del) {
                if (p->lchild == c)
                    p->lchild = nullptr;
                else
                    p->rchild = nullptr;
                delete c;
                root->color = BLACK;
                return;
            }
            p = c;
            c = del < *p->data ? p->lchild : p->rchild;
            t = c == p->lchild ? p->rchild : p->lchild;
        }
    }

    //迭代器擦除
    void erase(const iterator & x) {
        //判断是否为空
        if (x.currentData == nullptr)
            return;

        T * del = x.currentData->data;
        node * t, *p, *c;

        if (root == nullptr) return;
        if (root->data == del && root->lchild == nullptr && root->rchild == nullptr) {
            delete root;
            root = nullptr;
            return;
        }

        p = c = t = root;
        while (true) {
            removeAdjust(p, c, t, *del);
            if (c->data == del && c->lchild && c->rchild) {
                auto tmp = c->rchild;
                while (tmp->lchild)
                    tmp = tmp->lchild;
                if (tmp->parent != c) {
                    auto temp = *tmp;
                    tmp->parent = c->parent;
                    if (tmp->parent)
                        if (tmp->parent->lchild == c)
                            tmp->parent->lchild = tmp;
                        else tmp->parent->rchild = tmp;
                    else root = tmp;
                    tmp->lchild = c->lchild;
                    if (c->lchild) c->lchild->parent = tmp;
                    tmp->rchild = c->rchild;
                    if (c->rchild) c->rchild->parent = tmp;
                    tmp->color = c->color;

                    c->parent = temp.parent;
                    if (temp.parent->lchild == tmp)
                        temp.parent->lchild = c;
                    else temp.parent->rchild = c;
                    c->lchild = temp.lchild;
                    if (c->lchild) c->lchild->parent = c;
                    c->rchild = temp.rchild;
                    if (c->rchild) c->rchild->parent = c;
                    c->color = temp.color;
                }
                else {
                    auto temp = *tmp;
                    tmp->parent = c->parent;
                    if (tmp->parent)
                        if (tmp->parent->lchild == c)
                            tmp->parent->lchild = tmp;
                        else tmp->parent->rchild = tmp;
                    else root = tmp;
                    if (c->lchild == tmp) {
                        tmp->lchild = c;
                        tmp->rchild = c->rchild;
                        if (c->rchild) tmp->rchild->parent = tmp;
                    }
                    else {
                        tmp->rchild = c;
                        tmp->lchild = c->lchild;
                        if (c->lchild) tmp->lchild->parent = tmp;
                    }
                    c->parent = tmp;
                    c->lchild = temp.lchild;
                    c->rchild = temp.rchild;
                    if (c->lchild) c->lchild->parent = c;
                    if (c->rchild) c->rchild->parent = c;
                    tmp->color = c->color;
                    c->color = temp.color;
                }

                p = c = tmp;
                c = c->rchild;
                t = p->lchild;
                continue;
            }

            if (c->data == del) {
                if (p->lchild == c)
                    p->lchild = nullptr;
                else
                    p->rchild = nullptr;
                delete c;
                root->color = BLACK;
                return;
            }
            p = c;
            c = *del < *p->data ? p->lchild : p->rchild;
            t = c == p->lchild ? p->rchild : p->lchild;
        }
    }

    void erase(const iterator & from, const iterator & to) {
        if (from == end()) return;
        for (auto p = from; p != to;)
            erase(p++);
    }

    //迭代器起始
    iterator begin() {
        iterator result;
        auto p = root;
        if (p != nullptr)
            for (; p->lchild != nullptr;) {
                p = p->lchild;
            }
        result.currentData = p;
        return result;
    }

    //迭代器结束
    iterator end() {
        return *new iterator;
    }

    //重载赋值符号
    mSet<T> operator=(const mSet<T> & b) {
        clear();
        root = nullptr;
        if (b.root == nullptr)
            return *this;
        root = new node;
        copy(root, b.root);
        return *this;
    }

    //检查是否合法
    int check(node * pos) {
        int left = 0, right = 0;
        if (pos->lchild != nullptr)
            left = check(pos->lchild);
        if (pos->rchild != nullptr)
            right = check(pos->rchild);
        if (left < 0 || right < 0 || left != right)
            return -1;
        if (pos->color == BLACK)
            return 1 + left;
        else return left;
    }
};

//存放答案
mVector<int> ans;

//并查集
class disjointSet {
public:
    //数组
    int* parent;
    int length = 0;
    mSet<int>* edges;

    //构造函数
    disjointSet() = default;
    disjointSet(int size) :length(size) {
        parent = new int[size];
        edges = new mSet<int>[size];
        memset(parent, -1, length * sizeof(int));
    }

    //析构函数
    ~disjointSet() {
        length = 0;
        delete[] parent;
    }

    //寻找
    int find(int x) {
        int temp = x;
        for (; parent[temp] >= 0; temp = parent[temp]);
        //压缩路径
        for (int i = x; i != temp;) {
            int tempi = parent[i];
            parent[i] = temp;
            i = tempi;
        }
        return temp;
    }
    //合并
    void set_union(int root1, int root2) {
        if (root1 == root2)
            return;
        if (parent[root1] > parent[root2]) {
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
        else {
            parent[root1] += parent[root2];
            parent[root2] = root1;
        }
    }

    //BFS
    void bfs(int a, int b) {
        bool* visited = new bool[length]();
        int* last_visit = new int[length]();
        mQueue<int> mq;
        mq.push(a);
        while (!mq.empty()) {
            auto curPos = mq.front();
            visited[curPos] = true;
            mq.pop();
            if (curPos == b) {
                break;
            }
            for (auto p : edges[curPos]) {
                if (!visited[p]) {
                    mq.push(p);
                    last_visit[p] = curPos;
                }
            }
        }
        //反向搜索
        for (int i = b;; i = last_visit[i]) {
            ans.push_back(i);
            if (i == a)
                break;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, A, B;
    cin >> N >> A >> B;
    disjointSet dset(N*(N+1)/2+1);
    int pi, qi;
    while (cin >> pi >> qi) {
        //求出层和位置
        int n, pos;
        for (n = 1; n * (n + 1) / 2 < pi; n++);
        pos = pi - n * (n - 1) / 2;

        //砸墙
        if (qi == 0) {
            if (pos > 1 && n > 1) {
                dset.set_union(dset.find(pi), dset.find(pi - n));
                dset.edges[pi].insert(pi - n);
                dset.edges[pi - n].insert(pi);
            }
        }
        else if (qi == 1) {
            if (pos < n && n>1) {
                dset.set_union(dset.find(pi), dset.find(pi - n + 1));
                dset.edges[pi].insert(pi - n + 1);
                dset.edges[pi - n + 1].insert(pi);
            }
        }
        else if (qi == 2) {
            if (n < N){
                dset.set_union(dset.find(pi), dset.find(pi + n)); 
                dset.edges[pi].insert(pi + n);
                dset.edges[pi + n].insert(pi);
            }
        }
        else if (qi == 3) {
            if (n < N) {
                dset.set_union(dset.find(pi), dset.find(pi + n + 1));
                dset.edges[pi].insert(pi + n + 1);
                dset.edges[pi + n + 1].insert(pi);
            }
        }

        //判断是否有出入口
        if (dset.find(A) == dset.find(B)) {
            dset.bfs(A, B);
            cout << ans[ans.get_size() - 1];
            for (int i = ans.get_size() - 2; i >= 0; i--)
                cout << " " << ans[i];
            break;
        }
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

int disjoinSet[maxN] = {0}, map[1010][1010], cell[maxN][2], ans[maxN], N, A, B,
    sum;
bool isVisited[maxN] = {0}, wall[maxN][4] = {0}, found = 0;
int xPlus[] = {-1, -1, 1, 1}, yPlus[] = {-1, 0, 0, 1};

void generate();

int find(int);

void DFS(int, int, int, bool);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> A >> B;
    generate();

    do {
        int x, y;
        cin >> x >> y;
        wall[x][y] = 1;
        switch (y) {
            case 0:
                if (cell[x][1] > 1 && cell[x][0] > 1) {
                    int temp = map[cell[x][0] - 1][cell[x][1] - 1];
                    wall[temp][3] = 1;
                    x = find(x);
                    temp = find(temp);
                    if (temp >= 1 && temp <= sum) {
                        disjoinSet[temp] = disjoinSet[x];
                    }
                }
                break;
            case 1:
                if (cell[x][0] > 1) {
                    int temp = map[cell[x][0] - 1][cell[x][1]];
                    wall[temp][2] = 1;
                    x = find(x);
                    temp = find(temp);
                    if (temp >= 1 && temp <= sum) {
                        disjoinSet[temp] = disjoinSet[x];
                    }
                }
                break;
            case 2:
                if (cell[x][0] < N) {
                    int temp = map[cell[x][0] + 1][cell[x][1]];
                    wall[temp][1] = 1;
                    x = find(x);
                    temp = find(temp);
                    if (temp >= 1 && temp <= sum) {
                        disjoinSet[temp] = disjoinSet[x];
                    }
                }
                break;
            case 3:
                if (cell[x][0] < N) {
                    int temp = map[cell[x][0] + 1][cell[x][1] + 1];
                    wall[temp][0] = 1;
                    x = find(x);
                    temp = find(temp);
                    if (temp >= 1 && temp <= sum) {
                        disjoinSet[temp] = disjoinSet[x];
                    }
                }
                break;
        }
    } while (find(A) != find(B));

    DFS(A, B, 0, found);

    return 0;
}

void generate() {
    sum = 1;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            map[i][j] = sum;
            disjoinSet[sum] = sum;
            cell[sum][0] = i;
            cell[sum][1] = j;
            sum++;
        }
    }

    sum -= 1;
}

int find(int x) {
    if (x < 1 || x > sum) {
        return -1;
    }
    int stack[maxN], front = 0;

    while (disjoinSet[x] != x) {
        stack[front++] = x;
        x = disjoinSet[x];
    }

    for (int i = 0; i < front; i++) {
        disjoinSet[stack[i]] = x;
    }

    return x;
}

void DFS(int now, int end, int step, bool found) {
    if (found) {
        return;
    } else if (now == end) {
        ans[step++] = now;

        for (int i = 0; i < step; i++) {
            cout << ans[i] << ' ';
        }
        found = 1;
        return;
    }
    isVisited[now] = 1;
    ans[step++] = now;
    for (int i = 0; i < 4; i++) {
        if (!wall[now][i]) {
            continue;
        } else {
            int temp;
            temp = map[cell[now][0] + xPlus[i]][cell[now][1] + yPlus[i]];
            if (temp != 0 && !isVisited[temp] && (find(temp) == find(end))) {
                DFS(temp, end, step, found);
            }
        }
    }

    isVisited[now] = 0;
    step--;
}

yyong119's solution

#include <iostream>
using namespace std;

int N,A, B, P, Q, x, y;
bool *mark, **Path;
int *path, pos;

int bSearch(int P) {
    int l = 1, r = N;
    while (l <= r) {
        int mid = l + r >> 1;
        if ((mid * (mid + 1) >> 1) < P)l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

inline int getPosition(int x, int y) {
    return ((x * (x - 1) >> 1) + y);
}

class disjointSet {
private:
    int *parent;

public:
    disjointSet(int n) : parent(new int[n + 1]) {
        for (int i = 1; i <= n; ++i) parent[i] = -1;
    }
    ~disjointSet() {
        delete [] parent;
    }
    int find(int x) {
        if (parent[x] < 0) return x;
        else {
            int tmp = parent[x];
            while (parent[tmp] > 0)tmp = parent[tmp];
            int y;
            while (x != tmp) {
                y = parent[x];
                parent[x] = tmp;
                x = y;
            }
            return tmp;
        }
    }
    void Union(int root1, int root2) {

        if (root1 == root2)return;
        if (parent[root1] < parent[root2]) {
            parent[root1] += parent[root2];
            parent[root2] = root1;
        }
        else {
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
    }
};

bool dfs(int x, int y) {

    mark[getPosition(x, y)] = true;
    if (getPosition(x, y) == B) return true;
    if (Path[0][getPosition(x, y)] && !mark[getPosition(x - 1, y - 1)]) {
        if (dfs(x - 1, y - 1)) {
            path[pos++] = getPosition(x - 1, y - 1);
            return true;
        }
    }
    if (Path[1][getPosition(x, y)] && !mark[getPosition(x - 1, y)]) {
        if (dfs(x - 1, y)) {
            path[pos++] = getPosition(x - 1, y);
            return true;
        }
    }
    if (Path[2][getPosition(x, y)] && !mark[getPosition(x + 1, y)]) {
        if (dfs(x + 1, y)) {
            path[pos++] = getPosition(x + 1, y);
            return true;
        }
    }
    if (Path[3][getPosition(x, y)] && !mark[getPosition(x + 1, y + 1)]) {
        if (dfs(x + 1, y + 1)) {
            path[pos++] = getPosition(x + 1, y + 1);
            return true;
        }
    }
    return false;
}

void deleteData() {
    for (int i = 0; i < 4; ++i) delete[] Path[i];
    delete[] Path; delete[] mark; delete[] path;
}

int main() {

    ios::sync_with_stdio(false);
    cin >> N >> A >> B;
    Path = new bool* [4];
    for (int i = 0; i < 4; ++i)
        Path[i] = new bool[(N * (N + 1) >> 1) + 1]();
    disjointSet dJS(N * (N + 1) >> 1);
    while (cin >> P >> Q) {
        x = bSearch(P);
        y = P - (x * (x - 1) >> 1);
        switch (Q) {
        case 0:
            if (y != 1) {
                dJS.Union(dJS.find(P), dJS.find(P - x));
                Path[0][P] = Path[3][P - x] = true;
            }
            break;
        case 1:
            if (y != x) {
                dJS.Union(dJS.find(P), dJS.find(P - x + 1));
                Path[1][P] = Path[2][P - x + 1] = true;
            }
            break;
        case 2:
            if (x != N) {
                dJS.Union(dJS.find(P), dJS.find(P + x));
                Path[2][P] = Path[1][P + x] = true;
            }
            break;
        case 3:
            if (x != N) {
                dJS.Union(dJS.find(P), dJS.find(P + x + 1));
                Path[3][P] = Path[0][P + x + 1] = true;
            }
        }
        if (dJS.find(A) == dJS.find(B)) break;
    }
    x = bSearch(A);
    y = A - (x * (x - 1) >> 1);
    mark = new bool[(N * (N + 1) >> 1) + 1]();
    path = new int[(N * (N + 1) >> 1)]();
    if (dfs(x, y)) path[pos++] = A;
    for (int i = pos - 1; i > 0; --i) cout << path[i] << ' ';
    cout << path[0] << endl;
    deleteData();
    return 0;
}