結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー ry0u_yd
提出日時 2015-09-06 19:48:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,423 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 79,260 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 04:41:43
合計ジャッジ時間 1,308 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

int a[4][4] = { {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12},
                {13,14,15,0} };

int main() {
    vector< vector<int> > v(4,vector<int>(4));
    rep(i,4) rep(j,4) cin >> v[i][j];

    bool flag = true;
    int res = 0;

    rep(i,4) {
        rep(j,4) {
            if(v[i][j] == 0) {
                res = abs(i-3);
                continue;
            }

            queue<pair<pair<int,int>,int > > que;
            que.push(mp(mp(i,j),0));

            bool used[5][5];
            memset(used,0,sizeof(used));
            used[i][j] = true;

            int cost = 0;
            while(que.size()) {
                P p = que.front().first;
                int cnt = que.front().second;
                que.pop();
                
                int y = p.first;
                int x = p.second;

                if(v[i][j] == a[y][x]) {
                    cost = cnt;
                    break;
                }

                used[y][x] = true;

                rep(k,4) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];

                    if(0 <= ny && ny < 4 && 0 <= nx && nx < 4 && !used[ny][nx]) {
                        que.push(mp(mp(ny,nx),cnt+1));
                    }
                }
            }

            if(cost >= 2) {
                flag = false;
            }
        }
    }

    rep(i,4) {
        rep(j,4) {
            if(v[i][j] == 0) continue;
            REP(k,i,4) {
                if(k == i) {
                    REP(l,j+1,4) {
                        if(v[k][l] == 0) continue;
                        if(v[i][j] > v[k][l]) res++;
                    }
                } else {
                    rep(l,4) {
                        if(v[k][l] == 0) continue;
                        if(v[i][j] > v[k][l]) res++;
                    }
                }
            }
        }
    }


    if(flag && res%2 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}
0