列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

NPSC 2007 高中組 決賽 H.數字拼盤

說明：給你一個 3x3 的數字拼盤，裡面有 1 ~ 8 等八個數字，每次只能把和空格相鄰的一個數字移動過去，問你是不是可以在 20 步裡面，排回 1 2 3 | 4 5 6 | 7 8 0 的狀態。( | 表示換行)

解法：DFS 配合回溯法的技巧，將所有的可能展開，而如果超過 20 步則直接 return。我們可以順便記錄上一個步驟是什麼，避免馬上走回先前一步的狀態，如此可以加快程式的處理。

這類的問題，可用 8-puzzle、15-puzzle 等關鍵字到 google 查詢。

參考程式：(By sagit)

代碼: [選擇]

// NPSC 2007 決賽 - 題目 H - 數字拼盤 //
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int N=9, D=20;
int M[N], Found;

void DFS(int z, int d, int pre)
{
    int i;
    if ( Found ) return;
    for (i=0; i<N-1; i++) // 檢查是否完成
        if ( M[i] != (i+1) ) break;
    if ( i==N-1 ) // 已完成
    {
        Found=1;
        return;
    }
    if ( d>=D ) return; // 超過指定次數則不再繼續
    if ( z>2 && abs(pre-0)!=2 ) // 上
    {
        swap(M[z], M[z-3]);
        DFS(z-3, d+1, 0);
        swap(M[z], M[z-3]);
    }
    if ( z%3>0 && abs(pre-1)!=2 ) // 左
    {
        swap(M[z], M[z-1]);
        DFS(z-1, d+1, 1);
        swap(M[z], M[z-1]);
    }
    if ( z<6 && abs(pre-2)!=2 ) // 下
    {
        swap(M[z], M[z+3]);
        DFS(z+3, d+1, 2);
        swap(M[z], M[z+3]);
    }
    if ( z%3<2 && abs(pre-3)!=2 ) // 右
    {
        swap(M[z], M[z+1]);
        DFS(z+1, d+1, 3);
        swap(M[z], M[z+1]);
    }
}

int main()
{
    ifstream fin("ph.in");
    ofstream fout("ph.out");
    int k, i, z;

    fin >> k;
    while (k--)
    {
        for (i=0, Found=0; i<N; i++)
        {
            fin >> M[i];
            if ( M[i]==0 ) z=i; // 尋找 0 的位置
        }
        DFS(z, 0, -10);
        fout << ( Found ? "Easy" : "Hard" ) << endl;
    }

//    system("PAUSE");
    return 0;
}

[silithus]

晚上在ZeroJudge上看到有人挑戰這題，我也試著做，AC之後上網搜索下，發現大多數題解都是用DFS來做，以下是我的做法：
1. 從目標狀態[123|456|780]用BFS法倒推20步，把所有出現過的棋盤狀態記錄下來(我是用STL的set來維護)，總共有54802種狀態。
2. 由於用BFS搜得的路徑均為最短徑，若初始棋盤不在該集合中，所需的解題步數必然超過20步，因此答案為hard，否則為easy。
3. 用set來維護棋盤集合，每次查詢的時間複雜度均為常數，O(log₂集合總數) = log₂54802 = 16
4. 這個解法只需做一次BFS，之後以常數時間複雜度進行查詢，當詢問筆數越多時，效率會越明顯地較DFS法優勝。
若有錯處，歡迎指正。

代碼: [選擇]

/**********************************************************************************/
/*  Problem: b094 "H. 數字拼盤" from 2007 NPSC 高中組決賽                */
/*  Language: CPP (1352 Bytes)                                                    */
/*  Result: AC(28ms, 1.6MB) judge by this@ZeroJudge                               */
/*  Author: silithus at 2014-06-28 23:05:00                                       */
/**********************************************************************************/

#include <cstdio>
#include <queue>
#include <set>

#define WITHIN(n,a,b) ((a)<=(n) && (n)<=(b))

using namespace std;

int ten[10], mr[]={-1,-3,1,3};
set<int> status;

inline int find_zero(int n)
{
    for(int i=0; i<9; i++)
        if( ((n/ten[i]) % 10) == 0 )
            return i;
   
    return -1;
}

inline int exchange(int n, int s, int t)
{
    int u,v,d;
   
    u = (n/ten[s]) % 10;
    v = (n/ten[t]) % 10;
    d = u - v;
    n -= d * ten[s];
    n += d * ten[t];
   
    return n;
}

void BFS(void)
{
    int i,u,nu,z,nz,count,step;
    queue<int> que;
   
    u = 123456780;
    que.push(u);
    status.insert(u);
    count = que.size();
    step = 1;
   
    while( !que.empty() && step < 21 ) {
        u = que.front();
        que.pop();
        z = find_zero(u);
        for(i=0; i<4; i++) {
            nz = z + mr[i];
            if( WITHIN(nz, 0, 8) && !(z%3==0 && i==0) && !((z+1)%3==0 && i==2) ) {
                nu = exchange(u, z, nz);
                if( status.insert(nu).second )
                    que.push(nu);
            }
        }
       
        if( --count == 0 ) {
            count = que.size();
            ++step;
        }
    }
}

int main(void)
{
    int N,i,j,chess;

    for(i=ten[0]=1; i<10; i++)
        ten[i] = ten[i-1] * 10;

    BFS();

    scanf("%d", &N);
    while( N-- ) {
        for(i=chess=0; i<9; i++) {
            scanf("%d", &j);
            chess *= 10;
            chess += j;
        }

        printf("%s\n", status.count(chess) ? "Easy" : "Hard" );
    }

    return 0;
}