結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー mencottonmencotton
提出日時 2020-11-02 23:02:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,746 bytes
コンパイル時間 865 ms
コンパイル使用メモリ 83,228 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-22 08:16:16
合計ジャッジ時間 1,670 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 3 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 WA -
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 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