晚上在ZeroJudge上看到有人挑戰這題,我也試著做,AC之後上網搜索下,發現大多數題解都是用DFS來做,以下是我的做法:
1. 從目標狀態[123|456|780]用BFS法倒推20步,把所有出現過的棋盤狀態記錄下來(我是用STL的set來維護),總共有54802種狀態。
2. 由於用BFS搜得的路徑均為最短徑,若初始棋盤不在該集合中,所需的解題步數必然超過20步,因此答案為hard,否則為easy。
3. 用set來維護棋盤集合,每次查詢的時間複雜度均為常數,O(log2集合總數) = log254802 = 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;
}