結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー tetsuzuki1115tetsuzuki1115
提出日時 2017-09-28 02:44:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,789 bytes
コンパイル時間 625 ms
コンパイル使用メモリ 74,712 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-09 20:23:12
合計ジャッジ時間 1,783 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int Board[4][4];
int Board_Goal[4][4];
int Board_Used[4][4];

int direc[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

int dfs() {
    
    pair<int,int> index_zero;
    bool is_all_ok = true;
    for ( int i = 0; i < 4; i++ ) {
    for ( int j = 0; j < 4; j++ ) {
        if ( Board_Used[i][j] && Board_Used[i][j] != Board_Goal[i][j] ) {
            return 0;
        }
        if ( Board[i][j] != Board_Goal[i][j] ) { is_all_ok = false; }
        if ( !Board[i][j] ) { index_zero.first = i; index_zero.second = j; }
    }
    }
    if ( is_all_ok ) { return 1; }
    
    int ret = 0;
    for ( int i = 0; i < 4; i++ ) {
        int x0 = index_zero.first;
        int y0 = index_zero.second;
        int x1 = index_zero.first + direc[i][0];
        int y1 = index_zero.second + direc[i][1];
        
        if ( x1 >= 0 && y1 >= 0 && x1 < 4 && y1 < 4 && !Board_Used[x1][y1] ) {
            Board_Used[x0][y0] = Board[x1][y1];
            swap( Board[x0][y0], Board[x1][y1] );
            
            ret = max( ret, dfs() );
            
            Board_Used[x0][y0] = 0;
            swap( Board[x0][y0], Board[x1][y1] );
        }
        
        
    } 
    
    return ret;
}

int main() {
    
    for ( int i = 0; i < 4; i++ ) {
    for ( int j = 0; j < 4; j++ ) {
        int a;
        cin >> a;
        
        Board_Goal[i][j] = a;
        Board[i][j] = (i*4+j+1)%16;
        Board_Used[i][j] = 0;
    }
    }
    
    cout << ( dfs() ? "Yes" : "No" ) << endl;
    
    
    return 0;
}
0