結果
問題 |
No.228 ゆきこちゃんの 15 パズル
|
ユーザー |
![]() |
提出日時 | 2023-11-07 14:05:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 5,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 2,404 ms |
コンパイル使用メモリ | 212,124 KB |
最終ジャッジ日時 | 2025-02-17 19:56:44 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #include<iostream> #include<iomanip> #include<string> #include<algorithm> #include<vector> #include<set> #include<list> #include<queue> #include<math.h> #include<bitset> using ll = long long; using namespace std; int main(){ vector<vector<int>> v(4, vector<int>(4)), g(4, vector<int>(4)), s; vector<int> dx{1, 0, -1, 0}, dy{0, 1, 0, -1}; for (int i = 0; i < 4; i++){ for (int j = 0; j < 4; j++){ cin >> g[i][j]; v[i][j] = i*4 + j + 1; } } v[3][3] = 0; s = v; deque<vector<vector<int>>> dq; deque<vector<int>> pos; pos.push_back({3, 3}); dq.push_back(v); while (!pos.empty()) { vector<int> p_tmp = pos.front(); vector<vector<int>> v_tmp = dq.front(); pos.pop_front(); dq.pop_front(); if (g == v_tmp) { cout << "Yes" << endl; return 0; } for (int i = 0; i < 4; i++){ int nx, ny; nx = p_tmp[1] + dx[i]; ny = p_tmp[0] + dy[i]; vector<vector<int>> v_tmp2 = v_tmp; if (nx >= 0 && nx < 4 && ny >= 0 && ny <4 && v_tmp2[ny][nx] == s[ny][nx]){ swap(v_tmp2[ny][nx], v_tmp2[p_tmp[0]][p_tmp[1]]); dq.push_back(v_tmp2); pos.push_back({ny, nx}); } } } cout << "No" << endl; }