結果

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

ソースコード

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<bool>> ok(4, vector<bool>(4, true));

    pos emp;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int x;
            cin >> x;

            if (x == 0)x += 16, emp = {i, j};
            x--;

            int move = abs(i - (x / 4)) + abs(j - (x % 4));
            if (move > 1) {
                cout << "No" << endl;
                return 0;
            }
            if (move == 1)ok[i][j] = false;
        }
    }

    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) && !ok[next.x][next.y]) {
                ok[next.x][next.y] = true;
                que.push(next);
            }
        }
    }

    bool ret = true;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (!ok[i][j])ret = false;
        }
    }

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