結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー siman
提出日時 2016-03-25 04:04:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,616 bytes
コンパイル時間 1,393 ms
コンパイル使用メモリ 81,188 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-02 00:41:56
合計ジャッジ時間 2,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits.h>
#include <time.h>
#include <string>
#include <string.h>
#include <sstream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;

const int DY[4] = {-1, 0, 0, 1};
const int DX[4] = { 0,-1, 1, 0};

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

int field[4][4];
map<int, bool> checkList;

bool check(){
  for(int y = 0; y < 4; y++){
    for(int x = 0; x < 4; x++){
      if(correctField[y][x] != field[y][x]){
        return false;
      }
    }
  }

  return true;
}

bool success;

bool isOutside(int y, int x){
  return (y < 0 || 4 <= y || x < 0 || 4 <= x);
}

void dfs(int y, int x){
  if(y == 3 && x == 3 && check()){
    success = true;
  }

  for(int i = 0; i < 4; i++){
    int ny = y + DY[i];
    int nx = x + DX[i];

    if (isOutside(ny,nx)) continue;
    int num = field[ny][nx];
    if (checkList[num]) continue;
    checkList[num] = true;
    field[ny][nx] = field[y][x];
    field[y][x] = num;

    dfs(ny, nx);

    checkList[num] = false;
    field[y][x] = field[ny][nx];
    field[ny][nx] = num;
  }
}

int main(){
  int curY = 0;
  int curX = 0;

  for(int y = 0; y < 4; y++){
    for(int x = 0; x < 4; x++){
      cin >> field[y][x];

      if (field[y][x] == 0){
        curY = y;
        curX = x;
      }
    }
  }

  success = false;

  dfs(curY, curX);

  if (success) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}
0