Ruudukko

#include <iostream>
#include <random>
#include <iomanip>
#include <cstring>
#include <chrono>
#include <algorithm>
#include <cassert>
 
constexpr int MAX_SIZE {60 + 2};
 
 
struct input_t {
    int n, m, y1, x1, y2, x2;
    int gy {}, gx {};
 
    const std::string print() const {
        std::ostringstream oss;
        oss << "[gy: " << gy << ", gx: " << gx << "], " << n << " " << m << " " << y1 << " " << x1 << " " << y2 << " " << x2;
        return oss.str();
    }
 
    void validate_input() const {
        assert(n >= 1 && m >= 1);
        assert(n <= 50 && m <= 50);
        assert(y1 >= 1 && y2 >= 1);
        assert(x1 >= 1 && x2 >= 1);
        assert(y1 <= n && y2 <= n);
        assert(x1 <= m && x2 <= m);
        assert(y1 != y2 || x1 != x2);
    };
 
    bool is_solvable() const {
        bool v1_even {((y1 + x1) & 1) == 0};
        bool v2_even {((y2 + x2) & 1) == 0};
        bool invalid {false
            // one row or one column
            || (n == 1 && (std::min(x1, x2) > 1 || std::max(x1, x2) < m))
            || (m == 1 && (std::min(y1, y2) > 1 || std::max(y1, y2) < n))
            // black and white start/end
            // for 'odd' graphs only this one condition
            || (((m * n) & 1) == 1 && (!v1_even || !v2_even))
            // for 'even' graphs:
            || (((m * n) & 1) == 0 && n > 1 && m > 1 && ((v1_even == v2_even)
                // size 2
                || (n == 2 && m > 2 && x1 == x2 && x1 != 1 && x1 != m)
                || (m == 2 && n > 2 && y1 == y2 && y1 != 1 && y1 != n)
                // 3 x even, even x 3
                || (n == 3 && (m & 1) == 0 && ((!v1_even && (x1 < x2 - (y1 != 2))) || (v1_even && (x1 > x2 + (y1 != 2)))))
                || (m == 3 && (n & 1) == 0 && ((!v1_even && (y1 < y2 - (x1 != 2))) || (v1_even && (y1 > y2 + (x1 != 2)))))
            ))
        };
        return !invalid;
    };
 
    bool is_trivial() const {
        int miny {std::min(y1, y2)}, maxy {std::max(y1, y2)};
        int minx {std::min(x1, x2)}, maxx {std::max(x1, x2)};
        return {false
            // opposite corners
            || (((n & 1) == 1 || (m & 1) == 1) && miny == 1 && maxy == n && minx == 1 && maxx == m)
            // corners on same face
            || ((n & 1) == 0 && miny == 1 && maxy == n && (maxx == 1 || minx == m))
            || ((m & 1) == 0 && minx == 1 && maxx == m && (maxy == 1 || miny == n))
        };
    };
 
    void validate_solution(const std::string& path) const {
        int y {y1}, x {x1};
        validate_input();
        assert(path.size() == std::size_t(n * m - 1));
 
        char grid[MAX_SIZE][MAX_SIZE];
        std::memset(grid, 0, sizeof(grid));
        for (char d : path) {
            assert(y >= 1 && x >= 1);
            assert(y <= n && x <= m);
            assert(grid[y][x] == 0);
            grid[y][x] = 1;
            assert(d == 'R' || d == 'D' || d == 'L' || d == 'U');
            y += (d == 'D') - (d == 'U');
            x += (d == 'R') - (d == 'L');
        }
        assert(y == y2 && x == x2);
    }
};
 
 
struct brute_force_solver {
    char grid[MAX_SIZE][MAX_SIZE];
 
    const std::string operator () (const input_t& i) {
        std::memset(grid, 0, sizeof(grid));
        for (int y {}; y <= i.n + 1; y++) {
            grid[y][0] = grid[y][i.m + 1] = 1;
        }
        for (int x {1}; x <= i.m; x++) {
            grid[0][x] = grid[i.n + 1][x] = 1;
        }
 
        std::string path;
        path.reserve(i.n * i.m);
 
        auto search {[&](auto search, char d, int y, int x) {
            if (grid[y][x]) {
                return false;
            }
            if (y > 1 && x > 1 && y < i.n && x < i.m
                && (grid[y - 1][x] == grid[y + 1][x] && grid[y][x - 1] == grid[y][x + 1] && grid[y - 1][x] != grid[y][x - 1])
               ) {
                return false;
            }
            if (d != 0) {
                path.push_back(d);
            }
            bool found {};
            if (y == i.y2 && x == i.x2) {
                found = (path.size() == std::size_t(i.n * i.m - 1));
            } else {
                grid[y][x] = 1;
 
                found = (false
                    || (x < i.m && search(search, 'R', y, x + 1))
                    || (y < i.n && search(search, 'D', y + 1, x))
                    || (x > 1 && search(search, 'L', y, x - 1))
                    || (y > 1 && search(search, 'U', y - 1, x))
                );
 
                grid[y][x] = 0;
            }
            if (!found && d != 0) {
                path.pop_back();
            }
            return found;
        }};
 
        search(search, 0, i.y1, i.x1);
        if (!path.empty()) { i.validate_solution(path); }
        return path;
    }
};
 
struct solver_base {
    char grid[MAX_SIZE][MAX_SIZE];
    std::string indent;
 
    void solve_trivial_path(const input_t& i) {
        static char dir[] {"ULDR"};
 
        bool cols_first {((i.n & 1) == 0 && i.x1 != i.x2) || i.y1 == i.y2};
        bool rows_first {!cols_first};
 
        auto [n, m, y1, x1, y2, x2, gy, gx] {i};
        if (!rows_first) {
            std::swap(n, m);
            std::swap(y1, x1);
            std::swap(y2, x2);
        }
 
        int y {y1}, x {x1};
        int dy {(y2 > 1) - (y2 == 1)};
        int dx {(x2 > 1) - (x2 == 1)};
        if ((n & 1) == 0) { dx *= -1; };
 
        (rows_first ? gy : gx) += y;
        (rows_first ? gx : gy) += x;
        while (true) {
            for (int c {}; c < m - 1; c++) {
                assert(y > 0 && y <= n && x > 0 && x <= m);
                grid[gy][gx] = dir[1 + rows_first + dx];
                x += dx;
                (rows_first ? gx : gy) += dx;
            }
            if (y == y2) { break; }
            assert(y > 0 && y <= n && x > 0 && x <= m);
            grid[gy][gx] = dir[2 - rows_first + dy];
            y += dy;
            (rows_first ? gy : gx) += dy;
            dx *= -1;
        }
        assert(y == y2 && x == x2);
        grid[gy][gx] = 'e';
    }
 
    void print_subgrid(const input_t& i) {
        // print grid / sub-grid
        std::cout << indent << std::string(i.m + 2, '_') << std::endl;
        for (int y {1}; y <= i.n; y++) {
            std::cout << indent << std::quoted(std::string(grid[i.gy + y] + i.gx + 1, grid[i.gy + y] + i.gx + 1 + i.m), '_') << std::endl;
        }
        std::cout << indent << std::string(i.m + 2, '_') << std::endl;
        std::cout << std::endl;
    }
 
    const std::string path_from_grid(const input_t& i) const {
        std::string path;
        path.reserve(i.n * i.m);
        int y {i.y1};
        int x {i.x1};
        for (int c {}; c < i.n * i.m - 1; c++) {
            const char d {grid[i.gy + y][i.gx + x]};
            path.push_back(d);
            y += (d == 'D') - (d == 'U');
            x += (d == 'R') - (d == 'L');
        }
        return path;
    }
 
    virtual const bool solve(const input_t&) = 0;
 
    const std::string operator () (const input_t& i) {
        std::memset(grid, 0, sizeof(grid));
        for (int y {}; y <= i.n + 1; y++) {
            std::memset(grid[y], '_', i.m + 2);
        }
 
        auto solved {solve(i)};
        // std::cout << "solver: " << i.print() << " (solved: " << solved << ")" << std::endl;
        if (solved) {
            // print_subgrid(i);
            auto path {path_from_grid(i)};
            i.validate_solution(path);
            return path;
        }
        return {};
    }
};
 
struct solver : solver_base {
    bool solve_rec(const input_t& i) {
        bool is_solvable {i.is_solvable()}, is_trivial {i.is_trivial()};
        assert(!is_trivial || is_solvable);
        // std::cout << indent << "solve_rec: " << i.print() << " (is_solvable: " << is_solvable << ", is_trivial: " << is_trivial << ")" << std::endl;
        i.validate_input();
        if (!is_solvable) {
            return false;
        }
 
        auto& [n, m, y1, x1, y2, x2, gy, gx] {i};
        indent.push_back('\t');
 
        auto ret_true {[&]() {
            indent.pop_back();
            // std::cout << indent << "solved   : " << i.print() << " (is_solvable: " << is_solvable << ", is_trivial: " << is_trivial << ")" << std::endl;
            // print_subgrid(i);
            // auto path {path_from_grid(i)};
            // i.validate_solution(path);
            return true;
        }};
 
        if (is_trivial) {
            solve_trivial_path(i);
            return ret_true();
        }
 
        auto grid_get {[this, &i](int y, int x) {
            return grid[i.gy + y][i.gx + x];
        }};
        auto grid_set {[this, &i](int y, int x, char v) {
            grid[i.gy + y][i.gx + x] = v;
        }};
 
        int minx {std::min(x1, x2)}, maxx {std::max(x1, x2)};
        for (int ex {2}; ex < minx; ex++) {
            if (solve_rec({n, m - ex, y1, x1 - ex, y2, x2 - ex, gy, gx + ex})) {
                for (int y {1}; y < n; y++) {
                    bool dn {grid_get(y, ex + 1) == 'D'};
                    if (dn || grid_get(y + 1, ex + 1) == 'U') {
                        bool stripped {solve_rec({n, ex, y + 1 - dn, ex, y + dn, ex, gy, gx})};
                        assert(stripped);
                        grid_set(y + 1 - dn, ex + 1, 'L');
                        grid_set(y + dn, ex, 'R');
                        return ret_true();
                    }
                }
                assert(false);
            }
        }
        for (int ex {maxx}; ex < m - 1; ex++) {
            if (solve_rec({n, ex, y1, x1, y2, x2, gy, gx})) {
                for (int y {1}; y < n; y++) {
                    bool dn {grid_get(y, ex) == 'D'};
                    if (dn || grid_get(y + 1, ex) == 'U') {
                        bool stripped {solve_rec({n, m - ex, y + 1 - dn, 1, y + dn, 1, gy, gx + ex})};
                        assert(stripped);
                        grid_set(y + 1 - dn, ex, 'R');
                        grid_set(y + dn, ex + 1, 'L');
                        return ret_true();
                    }
                }
                assert(false);
            }
        }
        int miny {std::min(y1, y2)}, maxy {std::max(y1, y2)};
        for (int ey {2}; ey < miny; ey++) {
            if (solve_rec({n - ey, m, y1 - ey, x1, y2 - ey, x2, gy + ey, gx})) {
                for (int x {1}; x < m; x++) {
                    bool rh {grid_get(ey + 1, x) == 'R'};
                    if (rh || grid_get(ey + 1, x + 1) == 'L') {
                        bool stripped {solve_rec({ey, m, ey, x + 1 - rh, ey, x + rh, gy, gx})};
                        assert(stripped);
                        grid_set(ey + 1, x + 1 - rh, 'U');
                        grid_set(ey, x + rh, 'D');
                        return ret_true();
                    }
                }
                assert(false);
            }
        }
        for (int ey {maxy}; ey < n - 1; ey++) {
            if (solve_rec({ey, m, y1, x1, y2, x2, gy, gx})) {
                for (int x {1}; x < m; x++) {
                    bool rh {grid_get(ey, x) == 'R'};
                    if (rh || grid_get(ey, x + 1) == 'L') {
                        bool stripped {solve_rec({n - ey, m, 1, x + 1 - rh, 1, x + rh, gy + ey, gx})};
                        assert(stripped);
                        grid_set(ey, x + 1 - rh, 'D');
                        grid_set(ey + 1, x + rh, 'U');
                        return ret_true();
                    }
                }
                assert(false);
            }
        }
 
        for (int x {x1}; x < x2; x++) {
            for (int y {1}; y <= n; y++) {
                if ((y1 != y || x1 != x) && (y != y2 || x + 1 != x2)
                    && input_t {n, m - x, y, 1, y2, x2 - x}.is_solvable()
                    && solve_rec({n, x, y1, x1, y, x, gy, gx})
                    && solve_rec({n, m - x, y, 1, y2, x2 - x, gy, gx + x})
                ) {
                    grid_set(y, x, 'R');
                    return ret_true();
                }
            }
        }
        for (int x {x2}; x < x1; x++) {
            for (int y {1}; y <= n; y++) {
                if ((y1 != y || x1 != x + 1) && (y != y2 || x != x2)
                    && input_t {n, x, y, x, y2, x2}.is_solvable()
                    && solve_rec({n, m - x, y1, x1 - x, y, 1, gy, gx + x})
                    && solve_rec({n, x, y, x, y2, x2, gy, gx})
                ) {
                    grid_set(y, x + 1, 'L');
                    return ret_true();
                }
            }
        }
        for (int y {y1}; y < y2; y++) {
            for (int x {1}; x <= m; x++) {
                if ((y1 != y || x1 != x) && (y + 1 != y2 || x != x2)
                    && input_t {n - y, m, 1, x, y2 - y, x2}.is_solvable()
                    && solve_rec({y, m, y1, x1, y, x, gy, gx})
                    && solve_rec({n - y, m, 1, x, y2 - y, x2, gy + y, gx})
                ) {
                    grid_set(y, x, 'D');
                    return ret_true();
                }
            }
        }
        for (int y {y2}; y < y1; y++) {
            for (int x {1}; x <= m; x++) {
                if ((y1 != y + 1 || x1 != x) && (y != y2 || x != x2)
                    && input_t {y, m, y, x, y2, x2}.is_solvable()
                    && solve_rec({n - y, m, y1 - y, x1, 1, x, gy + y, gx})
                    && solve_rec({y, m, y, x, y2, x2, gy, gx})
                ) {
                    grid_set(y + 1, x, 'U');
                    return ret_true();
                }
            }
        }
        assert(false);
    }
 
    virtual const bool solve(const input_t& i) override final {
        return solve_rec(i);
    }
};
 
struct solver_tr : solver_base {
    struct input_tr_t : input_t {
        struct {
            bool transposed {};
            bool reflected {};
            int tn {}, tm {};
        } transformation;
 
        const std::string print() const {
            auto& t {transformation};
            std::ostringstream oss;
            oss << " [gy: " << gy << ", gx: " << gx << "], (tr: " << t.transposed << ", re: " << t.reflected << "): "
                << n << " " << m << " " << y1 << " " << x1 << " " << y2 << " " << x2;
            return oss.str();
        }
 
        void init_transformation() {
            transformation.tn = n + 1;
            transformation.tm = m + 1;
        }
 
        void set_transformation(bool transposed, bool reflected) {
            auto& [tr, re, tn, tm] {transformation};
            if (tr != transposed) {
                std::swap(n, m);
                std::swap(y1, x1);
                std::swap(y2, x2);
                std::swap(gy, gx);
                std::swap(tn, tm);
                tr = transposed;
            }
            if (re != reflected) {
                y1 = n + 1 - y1;
                x1 = m + 1 - x1;
                y2 = n + 1 - y2;
                x2 = m + 1 - x2;
                gy = tn - gy - n - 1;
                gx = tm - gx - m - 1;
                re = reflected;
            }
        }
 
        const std::pair<int, int> transform_yx(int y, int x) const {
            auto& [tr, re, tn, tm] {transformation};
            y = gy + y;
            x = gx + x;
            if (re) {
                y = tn - y;
                x = tm - x;
            }
            if (tr) {
                std::swap(y, x);
            }
            return {y, x};
        }
 
        const char transform_direction(char v) const {
            if (v == 'e') {
                return v;
            }
 
            auto& [tr, re, tn, tm] {transformation};
            if (re) {
                static char from[] {"RDLU"};
                static char to  [] {"LURD"};
                auto it {std::find(std::begin(from), std::end(from), v)};
                assert(it != std::end(from));
                v = to[it - std::begin(from)];
            }
            if (tr) {
                static char from[] {"RDLU"};
                static char to  [] {"DRUL"};
                auto it {std::find(std::begin(from), std::end(from), v)};
                assert(it != std::end(from));
                v = to[it - std::begin(from)];
            }
 
            return v;
        }
    };
 
    bool solve_rec(input_tr_t&& i) {
        bool is_solvable {i.is_solvable()}, is_trivial {i.is_trivial()};
        assert(!is_trivial || is_solvable);
        // std::cout << indent << "solve_rec: " << i.print() << " (is_solvable: " << is_solvable << ", is_trivial: " << is_trivial << ")" << std::endl;
        i.validate_input();
        if (!is_solvable) {
            return false;
        }
 
        auto& [n, m, y1, x1, y2, x2, gy, gx] {static_cast<input_t&>(i)};
        auto& t {i.transformation};
        indent.push_back('\t');
 
        auto ret_true {[&] {
            indent.pop_back();
            // i.set_transformation(false, false);
            // std::cout << indent << "solved   : " << i.print() << " (is_solvable: " << is_solvable << ", is_trivial: " << is_trivial << ")" << std::endl;
            // print_subgrid(i);
            // auto path {path_from_grid(i)};
            // i.validate_solution(path);
            return true;
        }};
 
        if (is_trivial) {
            i.set_transformation(false, false);
            solve_trivial_path(i);
            return ret_true();
        }
 
        auto grid_get {[this, &i](int y, int x) {
            auto [y_, x_] {i.transform_yx(y, x)};
            return i.transform_direction(grid[y_][x_]);
        }};
        auto grid_set {[this, &i](int y, int x, char v) {
            auto [y_, x_] {i.transform_yx(y, x)};
            grid[y_][x_] = i.transform_direction(v);
        }};
 
        for (auto& [tr, re] : std::initializer_list<std::pair<bool, bool>> {
            {t.transposed, t.reflected}, {!t.transposed, t.reflected},
            {!t.transposed, !t.reflected}, {t.transposed, !t.reflected}
        }) {
            i.set_transformation(tr, re);
 
            int minx {std::min(x1, x2)};
            for (int ex {2}; ex < minx; ex++) {
                if (solve_rec({n, m - ex, y1, x1 - ex, y2, x2 - ex, gy, gx + ex, t})) {
                    for (int y {1}; y < n; y++) {
                        bool dn {grid_get(y, ex + 1) == 'D'};
                        if (dn || grid_get(y + 1, ex + 1) == 'U') {
                            bool stripped {solve_rec({n, ex, y + 1 - dn, ex, y + dn, ex, gy, gx, t})};
                            assert(stripped);
                            grid_set(y + 1 - dn, ex + 1, 'L');
                            grid_set(y + dn, ex, 'R');
                            return ret_true();
                        }
                    }
                    assert(false);
                }
            }
            for (int x {x1}; x < x2; x++) {
                for (int y {1}; y <= n; y++) {
                    if ((y1 != y || x1 != x) && (y != y2 || x + 1 != x2)
                        && input_t {n, m - x, y, 1, y2, x2 - x}.is_solvable()
                        && solve_rec({n, x, y1, x1, y, x, gy, gx, t})
                        && solve_rec({n, m - x, y, 1, y2, x2 - x, gy, gx + x, t})
                    ) {
                        grid_set(y, x, 'R');
                        return ret_true();
                    }
                }
            }
        }
        assert(false);
    }
 
    virtual const bool solve(const input_t& i_) override final {
        input_tr_t i {i_};
        i.init_transformation();
        return solve_rec(std::move(i));
    }
};
 
 
const input_t rand_input(int max_size, int r) {
    static std::random_device rd;
    static std::mt19937 re {rd()};
    assert(max_size >= 1 && max_size <= 50);
 
    std::uniform_int_distribution<int> diff_uniform_dist {0, max_size - 1};
    int ydiff {diff_uniform_dist(re)}, xdiff{diff_uniform_dist(re)};
    if (ydiff == 0 && xdiff == 0) {
        ydiff += 1 - (r & 1);
        xdiff += (r & 1);
    }
 
    input_t i;
    i.n = std::uniform_int_distribution<int> {ydiff + 1, max_size}(re);
    i.m = std::uniform_int_distribution<int> {xdiff + 1, max_size}(re);
 
    i.y1 = std::uniform_int_distribution<int> {1, i.n - ydiff}(re);
    i.x1 = std::uniform_int_distribution<int> {1, i.m - xdiff}(re);
    i.y2 = i.y1 + ydiff;
    i.x2 = i.x1 + xdiff;
 
    if (r & 2) {
        std::swap(i.y1, i.y2);
    }
    if (r & 4) {
        std::swap(i.x1, i.x2);
    }
 
    i.validate_input();
    return i;
}
 
void test(int num, int max_size, bool cmp) {
    auto measure_execution {[](auto& timer, auto callable, auto... args) -> decltype(auto) {
        auto start {std::chrono::high_resolution_clock::now()};
        decltype(auto) ret {callable(std::forward<decltype(args)>(args)...)};
        auto finish {std::chrono::high_resolution_clock::now()};
        timer += std::chrono::duration_cast<std::remove_reference_t<decltype(timer)>>(finish - start);
        return ret;
    }};
 
    std::chrono::nanoseconds s_timer {}, s_tr_timer {}, bf_timer {};
 
    while (num-- > 0) {
        auto i {rand_input(max_size, num)};
        std::cout << "rand: " << i.print() << std::endl;
        auto s {measure_execution(s_timer, solver(), i)};
        std::cout << (s.empty() ? "NO" : "YES\n" + s) << std::endl;
        auto s_tr {measure_execution(s_tr_timer, solver_tr(), i)};
        std::cout << (s_tr.empty() ? "NO" : "YES\n" + s_tr) << std::endl;
        assert(s.empty() == s_tr.empty());
        if (cmp) {
            auto bf {measure_execution(bf_timer, brute_force_solver(), i)};
            std::cout << (bf.empty() ? "NO" : "YES\n" + bf) << std::endl;
            assert(s.empty() == bf.empty());
        }
    }
 
    std::cout << "s_timer: " << s_timer.count() / 1e9 << ", s_tr_timer: " << s_tr_timer.count() / 1e9
        << ", bf_timer: " << bf_timer.count() / 1e9 << std::endl << std::endl;
}
 
 
int main(int argc, char* argv[]) {
    // test(10000, 5, true);
    // test(10000, 12, false);
    // test(100000, 50, false);
 
    int t;
    input_t i;
    std::cin >> t;
    while (t-- > 0) {
        std::cin >> i.n >> i.m >> i.y1 >> i.x1 >> i.y2 >> i.x2;
        // std::cout << "cin: " << i.print() << std::endl;
        i.validate_input();
        auto s {solver()(i)};
        std::cout << (s.empty() ? "NO" : "YES\n" + s) << std::endl;
    }
    return 0;
}

Test 1

Group: 1, 5

Verdict: ACCEPTED

Test 2

Group: 2, 5

Verdict: ACCEPTED

Test 3

Group: 3, 5

Verdict: ACCEPTED

Test 4

Group: 4, 5

Verdict: ACCEPTED

Test 5

Group: 5

Verdict: ACCEPTED

Test 6

Group: 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 5

Verdict: ACCEPTED

Test 10

Group: 3, 5

Verdict: ACCEPTED

Test 11

Group: 3, 5

Verdict: ACCEPTED

Test 12

Group: 3, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 5

Verdict: ACCEPTED

Test 15

Group: 3, 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED