結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー Naco
提出日時 2019-10-25 14:35:36
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,164 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,655 ms
コンパイル使用メモリ 171,996 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 17:06:08
合計ジャッジ時間 2,218 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int A[4][4];
int S[4][4];

void solve(){
    queue<P> que;
    int k=1;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            S[i][j]=k;
            k++;
        }
    }
    S[3][3]=0;
    que.push({3,3});
    while(!que.empty()){
        P q=que.front(); que.pop();
        int x=q.first; int y=q.second;
        if(A[x][y]==0&&S[x][y]==0){
            break;
        }
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0||ny<0||nx>3||ny>3) continue;
            if(A[x][y]==S[nx][ny]){
                que.push({nx,ny});
                S[x][y]=A[x][y];
                S[nx][ny]=0;
                break;
            }
        }
    }
}

int main(){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            cin >> A[i][j];
        }
    }
    solve();
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(S[i][j]!=A[i][j]){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;

}
0