結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー mencotton
提出日時 2020-11-02 23:05:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,600 bytes
コンパイル時間 720 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-22 08:16:35
合計ジャッジ時間 1,405 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using ll = long long;

struct pos {
    int x, y;
    pos operator+(pos &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }
    pos &operator+=(const pos &rhs) {
        x += rhs.x, y += rhs.y;
        return *this;
    }
    bool operator==(pos &rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

const vector<pos> moves{{1,  0},
                        {-1, 0},
                        {0,  1},
                        {0,  -1}};

const int w = 4, h = 4;

bool inRange(pos p) {
    return 0 <= p.x && p.x < h && 0 <= p.y && p.y < w;
}

int main() {
    vector<vector<int>> ban(4, vector<int>(4));

    pos emp;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> ban[i][j];
            if (ban[i][j] == 0) {
                emp = {i, j};
                continue;
            }
        }
    }

    queue<pos> que;
    que.push(emp);
    while (!que.empty()) {
        pos here = que.front();
        que.pop();

        for (auto move:moves) {
            pos next = here + move;
            if (inRange(next) && ban[next.x][next.y] == here.x * 4 + here.y + 1) {
                ban[here.x][here.y] = ban[next.x][next.y], ban[next.x][next.y] = 0;
                que.push(next);
            }
        }
    }

    bool ret = true;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (ban[i][j] != (i * 4 + j + 1) % 16)ret = false;
        }
    }

    cout << (ret ? "Yes" : "No") << endl;
    return 0;
}
0