Submission #46166606

---

Source Code Expand

#include <set>
#include <vector>
#include <utility>
#include <cassert>
#include <iostream>

#define DEBUG(x) x
#define INFO(x) DEBUG(std::cerr << x << std::endl)
#define snap(var) DEBUG(std::cerr << "[snap] " << #var << " = " << (var) << std::endl)
#define snap_msg(msg, var) DEBUG(std::cerr << "[snap:" << (msg) << "] " << #var << " = " << (var) << std::endl)
#define assert_equal(x, y) assert_eq(x, y, #x " == " #y " is not satisfied!")
///---------------------------------------------------------------------
// utility

struct Point {
    int i;
    int j;
    Point() : i(0), j(0) {}
    Point(int x, int y) : i(x), j(y) {}
};
template<typename T>
using Row = std::vector<T>;
template<typename T>
using Grid = std::vector<Row<T>>;

bool operator<(const Point& p, const Point& q){
    return p.j * 4 + p.i < q.j * 4 + q.i;
}
bool operator==(const Point& p, const Point& q){
    return p.i == q.i and p.j == q.j;
}


std::ostream& operator<<(std::ostream& os, const Grid<char>& g) {
    os << std::endl;
    for (const Row<char>& r : g) {
        for (const char c : r) { os << c; }
        os << std::endl;
    }
    return os;
} 
std::ostream& operator<<(std::ostream& os, const Point& p) {
    return os << "(" << p.i << ", " << p.j << ")";
}
std::ostream& operator<<(std::ostream& os, const std::set<Point>& g) {
    os << std::endl;
    for (const Point& r : g) {
        os << r << ", ";
        os << std::endl;
    }
    return os;
} 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2> points) {
    return os << "[" << points.first << ", " << points.second << "]";
} 

template<typename T>
void assert_eq(const T& a, const T& b, const char* str) {
    if (a != b) {
        std::cerr << str << std::endl;
        snap(a);
        snap(b);
        assert(0);
    }
}

// utility
///---------------------------------------------------------------------

std::set<Point> convert_grid_to_set(const Grid<char>& grid){
    std::set<Point> placed_points_set;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (grid[i][j] == '#') {
                placed_points_set.insert({i, j});
            }
        }
    }
    return placed_points_set;
}

std::set<Point> shift(const std::set<Point>& before, const Point& delta) {
    std::set<Point> after;
    for (const Point& p : before) {
        after.insert({p.i + delta.i, p.j + delta.j});
    }
    return after;
}

std::set<Point> shift_to_left(const std::set<Point>& before){
    Point min{3, 3};
    for (const Point& p:before) {
        min.i = std::min(p.i, min.i);
        min.j = std::min(p.j, min.j);
    }
    return shift(before, {-min.i, -min.j});
}

std::set<Point> rotate90deg(const std::set<Point>& before){
    std::set<Point> after;
    for (const auto point:before) {
        after.insert({3 - point.j, point.i});
    }
    return after;
}
std::pair<Point, Point> bounding_box(const std::set<Point>& board) {
    Point min{3, 3}, max{-1, -1};
    for (const Point& p:board){
        min.i = std::min(p.i, min.i);
        min.j = std::min(p.j, min.j);
        max.i = std::max(p.i, max.i);
        max.j = std::max(p.j, max.j);
    }
    return {min, max};
}

bool is_valid(const std::set<Point>& board) {
    // 領域から外れていないか
    const auto [min, max] = bounding_box(board);
    if (
        min.i < 0 or min.j < 0 or
        max.i > 3 or max.j > 3
    ) { return false; }
    // ここにsetを使う意味がある。 (1)
    return board.size() == 16;
}

/// @brief ポリオミノpolyomino_pointsを位置placed_pointに置いた時に、条件を満たしうるかを深さ優先探索によって探索する。
/// @param board -- 参照をとっていない点に注意; placed_points_num番目のポリオミノを置いた時のボードの状況を示す。
bool possible_proper_placing(
    std::set<Point> board, 
    const std::set<Point>& polyomino_points, 
    const std::vector<std::set<Point>>& polyominos, 
    const int placed_poly_number
){
    // ここにsetを使う意味がある。 (2)
    for (const auto& point : polyomino_points) {
        // 外側に置かれている場合はfalse
        if (point.i < 0 or 4 <= point.i) { return false; }
        if (point.j < 0 or 4 <= point.j) { return false; }
        // すでにブロックが置かれていた場合はfalse
        if (board.count(point) > 0) { return false; }
        board.insert(point);
    }

    // 全てのポリオミノを置いているときは、その判定が正しいか判定する
    if (placed_poly_number == 2) { return is_valid(board); }

    // 右端に正規化しているので、16マスの置き方を走査すれば十分
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            // 回転4方向を探索する
            std::set<Point> rotated_polyomino = shift(polyominos[placed_poly_number + 1], {i, j});
            for (int r = 0; r < 4; r++) {
                // 可能性があったなら、上の枝にそのことを通知する。
                if (possible_proper_placing(board, rotated_polyomino, polyominos, placed_poly_number + 1)) {
                    return true;
                }
                // 公式解答参照
                rotated_polyomino = rotate90deg(rotated_polyomino);
            }
        }
    }
    return false;    
}


///---------------------------------------------------------------------
// テスト

void test(){
    {
        std::set<Point> points = {
            {1, 2},
            {0, 0},
        };
        const auto converted1 = std::set<Point>{Point(1, 1), Point(3, 0)};
        assert_equal(rotate90deg(points), converted1);
        const auto converted2 = std::pair<Point, Point>{Point(0, 0), Point(1, 2)};
        assert_equal(bounding_box(points), converted2);
    }
    {
        std::set<Point> points = {
            {1, 2},
            {2, 1},
        };
        const auto converted = std::set<Point>{Point(0, 1), Point(1, 0)};
        assert_equal(shift_to_left(points), converted);
    }
    {
        std::set<Point> points = {
            {0, 0}, {0, 1}, {0, 2}, {0, 3},
            {1, 0}, {1, 1}, {1, 2}, {1, 3},
            {2, 0}, {2, 1}, {2, 2}, {2, 3},
            {3, 0}, {3, 1}, {3, 2}, {3, 3},
        };
        assert_equal(is_valid(points), true);
    }
    {
        std::set<Point> points = {
            {0, 0}, {0, 1}, {0, 2}, {0, 3},
            {1, 0}, {1, 1}, {1, 2}, {1, 3},
            {2, 0}, {2, 1}, {2, 2}, {2, 3},
            {3, 0}, {3, 1}, {3, 2}, {3, 3},
            {3, 4}
        };
        assert_equal(is_valid(points), false);
    }
    
}

///---------------------------------------------------------------------

int main(){
    test();

    std::vector<Grid<char>> polyominos(3,
        Grid<char>(4, Row<char>(4))
    );
    for (int p = 0; p < 3; p++) {
        Grid<char>& polyomino = polyominos[p];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                std::cin >> polyomino[i][j];
            }
        }
    }
    snap(polyominos[0]);
    snap(polyominos[1]);
    snap(polyominos[2]);
    
    std::vector<std::set<Point>> pointsets = {
        shift_to_left(convert_grid_to_set(polyominos[0])),
        shift_to_left(convert_grid_to_set(polyominos[1])),
        shift_to_left(convert_grid_to_set(polyominos[2])),
    };
    assert(pointsets.size() == 3);

    std::set<Point> board;  
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {   
            if (possible_proper_placing(board, shift(pointsets[0], {i, j}), pointsets, 0)) {
                std::cout << "Yes" << std::endl;
                return 0;
            }
        }
    }
    std::cout << "No" << std::endl;

    return 0;
}

Submission Info

Judge Result