Gap
| Time Limit: 5000MS | Memory Limit: 65536K |
| Total Submissions: 1943 | Accepted: 889 |
Description
Let's play a card game called Gap.
You have 28 cards labeled with two-digit numbers. The first digit (from 1 to 4) represents the suit of the card, and the second digit (from 1 to 7) represents the value of the card.
First, you shu2e the cards and lay them face up on the table in four rows of seven cards, leaving a space of one card at the extreme left of each row. The following shows an example of initial layout.
Next, you remove all cards of value 1, and put them in the open space at the left end of the rows: "11" to the top row, "21" to the next, and so on.
Now you have 28 cards and four spaces, called gaps, in four rows and eight columns. You start moving cards from this layout.
At each move, you choose one of the four gaps and fill it with the successor of the left neighbor of the gap. The successor of a card is the next card in the same suit, when it exists. For instance the successor of "42" is "43", and "27" has no successor.
In the above layout, you can move "43" to the gap at the right of "42", or "36" to the gap at the right of "35". If you move "43", a new gap is generated to the right of "16". You cannot move any card to the right of a card of value 7, nor to the right of a gap.
The goal of the game is, by choosing clever moves, to make four ascending sequences of the same suit, as follows.
Your task is to find the minimum number of moves to reach the goal layout.
Input
The input starts with a line containing the number of initial layouts that follow.
Each layout consists of five lines - a blank line and four lines which represent initial layouts of four rows. Each row has seven two-digit numbers which correspond to the cards.
Output
For each initial layout, produce a line with the minimum number of moves to reach the goal layout. Note that this number should not include the initial four moves of the cards of value 1. If there is no move sequence from the initial layout to the goal layout, produce "-1".
Sample Input
4
12 13 14 15 16 17 21
22 23 24 25 26 27 31
32 33 34 35 36 37 41
42 43 44 45 46 47 11
26 31 13 44 21 24 42
17 45 23 25 41 36 11
46 34 14 12 37 32 47
16 43 27 35 22 33 15
17 12 16 13 15 14 11
27 22 26 23 25 24 21
37 32 36 33 35 34 31
47 42 46 43 45 44 41
27 14 22 35 32 46 33
13 17 36 24 44 21 15
43 16 45 47 23 11 26
25 37 41 34 42 12 31
Sample Output
0
33
60
-1
題意：給出一個表，搜先把每行的第一個數移動到正确的位置，問你最少多少步能把輸入的表變成目标狀态（題中圖3），移動到空位的數字必須滿足比他前面一個數大1；
思路：很明顯用到bfs去搜，關鍵書這麼儲存每個圖的狀态，看了一下學長部落格，可以用hash來存，也可以用到map，hash也就是将每個圖轉變成了一個相應的值，每個圖對應的hash值是不一樣的，也可能出現相同的情況，那就需要用到一些其他的方法改進一下，但是這題我參照的學長的方法算的hash值不會出現上述的情況，建構函數感覺是很重要的一步。寫的第一道用hash的題目~
AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#define mod 1000007
using namespace std;
typedef long long LL;
int mp[4][8];
LL Hash[mod];
LL base[32];
struct node
{
int mp[4][8];//存整個表
int tx[5],ty[5];//儲存4個空
int step;//記錄步數
}q,tmp;
queue<node> que;
int aim[4][8]={//目标狀态
11,12,13,14,15,16,17,0,
21,22,23,24,25,26,27,0,
31,32,33,34,35,36,37,0,
41,42,43,44,45,46,47,0,
};
LL goal;//目标狀态的hash值
void Getbase()
{
base[0]=1;
for(int i=1;i<32;i++)
base[i]=base[i-1]*2;
}
LL GetHash(int arr[4][8])//算每個狀态的hash值
{
LL sum=0;
for(int i=0;i<4;i++){
for(int j=0;j<8;j++){
sum+=arr[i][j]*base[i*8+j];
}
}
return sum;
}
void change(node& t,int x,int y,int val,int k)//将某個點的值填到一個空位
{
for(int i=0;i<4;i++){
for(int j=0;j<8;j++){
if(t.mp[i][j]==val){
t.mp[i][j]=0;
t.mp[x][y]=val;
t.tx[k]=i;//記錄新的空位
t.ty[k]=j;
return;
}
}
}
}
bool Insert_Hash(node q)//判斷能否插入，判重
{
LL sum=GetHash(q.mp);
int v=sum%mod;
while(Hash[v]!=-1&&Hash[v]!=sum) v=(v+10)%mod;
if(Hash[v]==-1){Hash[v]=sum;return true;}
return false;
}
int bfs()
{
while(que.size())
{
tmp=que.front();
que.pop();
if(GetHash(tmp.mp)==goal) return tmp.step;//該點hash值和目标值相等，說明改狀态即為目标狀态，傳回相應的值
for(int i=1;i<=4;i++)//循環4個空位
{
int pre=tmp.mp[tmp.tx[i]][tmp.ty[i]-1];
if(pre==0)continue;//該空位前面一個也是空點不行
if(pre%10==7)continue;//該空位前面一個是每行最大的數不行
q=tmp;
int tt=pre+1;
change(q,q.tx[i],q.ty[i],tt,i);
if(!Insert_Hash(q))continue;
q.step=tmp.step+1;
que.push(q);
}
}
return -1;
}
void init()
{
Getbase();
goal=GetHash(aim);
memset(Hash,-1,sizeof(Hash));
for(int i=0;i<4;i++){
for(int j=0;j<8;j++){
if(j==0){q.mp[i][j]=0;continue;}//每一行第一個點置為空點
scanf("%d",&q.mp[i][j]);
}
}
int cnt=0;
for(int i=0;i<4;i++){
for(int j=0;j<8;j++){//找到每行的第一個數
if(q.mp[i][j]==11&&j){
q.mp[0][0]=11;q.mp[i][j]=0;
q.tx[++cnt]=i;q.ty[cnt]=j;
}
if(q.mp[i][j]==21&&j){
q.mp[1][0]=21;q.mp[i][j]=0;
q.tx[++cnt]=i;q.ty[cnt]=j;
}
if(q.mp[i][j]==31&&j){
q.mp[2][0]=31;q.mp[i][j]=0;
q.tx[++cnt]=i;q.ty[cnt]=j;
}
if(q.mp[i][j]==41&&j){
q.mp[3][0]=41;q.mp[i][j]=0;
q.tx[++cnt]=i;q.ty[cnt]=j;
}
}
}
q.step=0;
que.push(q);
}
int main()
{
int t;
cin>>t;
while(t--)
{
init();
printf("%d\n",bfs());
while(que.size())que.pop();
}
return 0;
}