結果
問題 | No.228 ゆきこちゃんの 15 パズル |
ユーザー |
|
提出日時 | 2016-11-24 18:23:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 5,000 ms |
コード長 | 1,494 bytes |
コンパイル時間 | 2,133 ms |
コンパイル使用メモリ | 190,252 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 10:36:10 |
合計ジャッジ時間 | 3,349 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; typedef vector< int > vi; typedef vector< vi > vvi; set< tuple< vvi, int > > vis; int in_range( int x, int y ){ return 0 <= x and x < 4 and 0 <= y and y < 4; } signed main(){ vvi gol( 4, vi( 4 ) ); for( int i = 0; i < 4; ++i ) for( int j = 0; j < 4; ++j ) gol[ i ][ j ] = i * 4 + j + 1; gol[ 3 ][ 3 ] = 0; vvi A( 4, vi( 4 ) ); for( int i = 0; i < 4; ++i ) for( int j = 0; j < 4; ++j ) cin >> A[ i ][ j ]; queue< tuple< vvi, int > > que; que.emplace( gol, 0 ); vis.emplace( gol, 0 ); while( not que.empty() ){ vvi u; int s; tie( u, s ) = que.front(); que.pop(); for( int i = 0; i < 4; ++i ) for( int j = 0; j < 4; ++j ) if( u[ i ][ j ] == 0 ){ for( int di = 0; di < 4; ++di ){ int ni = i + dx[ di ]; int nj = j + dy[ di ]; if( not in_range( ni, nj ) ) continue; if( s >> u[ ni ][ nj ] & 1 ) continue; swap( u[ i ][ j ], u[ ni ][ nj ] ); if( not vis.count( make_tuple( u, s | 1 << u[ i ][ j ] ) ) ) que.emplace( u, s | 1 << u[ i ][ j ] ), vis.emplace( u, s | 1 << u[ i ][ j ] ); swap( u[ i ][ j ], u[ ni ][ nj ] ); } } } for( int i = 0; i < 1 << 16; ++i ) if( vis.count( make_tuple( A, i ) ) ) cout << "Yes" << endl, exit( 0 ); cout << "No" << endl; return 0; }