結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー mencottonmencotton
提出日時 2020-11-02 23:02:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,746 bytes
コンパイル時間 822 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-29 14:01:52
合計ジャッジ時間 1,746 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,384 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,384 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,384 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 WA -
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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) {
                emp = {i, j};
                continue;
            }

            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