码农场
滑动拼图：也许你玩过15拼图：
可你玩过28拼图吗？给定4*8的表格
首先把11、21、31、41这四个数字提到第一列空白处：
然后按如下规则移动数字，定义某个空白处的左邻居+1为魔法数字，如果魔法数字存在，则可以将该魔法数字移动到该空白，比如42旁边的空白可以填充的魔法数字为43，而27则没有魔法数字，因为根本不存在28这个数。
拼图的目标是达到如下效果：
求最小移动回数。
4.5开动脑筋智慧搜索
剪枝
题目本身没什么难度，模拟一个游戏规则，用BFS遍历所有状态。
复杂之处在于状态数非常之多，32个格子，28种数字，状态数一共有
不可能用visited[]数组在内存里都表达出来，可以用HashSet来记录visited状态。由于C++98里面没有好用的HashSet，而陈腐的POJ又不支持C++11，所以干脆提交到了AOJ上去了
。
#include <iostream>
#include <cstring>
#include <climits>
#include <queue>
#include <unordered_set>
using namespace std;
class State
{
public:
/**
* 表格数字
*/
int table[4][8];
/**
* 移动回数
*/
int turn;
State(int card[4][7])
{
for (int i = 0; i < 4; i++)
table[i][0] = (10 * (i + 1) + 1);// 11 21 31 41
for (int i = 0; i < 4; i++)
{
memcpy(table[i] + 1, card[i], 7 * sizeof(int));
}
// 从这种布局开始游戏
for (int i = 0; i < 4; i++)
{
for (int j = 1; j < 8; j++)
{
if (table[i][j] == 11 || table[i][j] == 21 || table[i][j] == 31 || table[i][j] == 41)
table[i][j] = 0;
}
}
turn = 0;
}
State(const State &t)
{
memcpy(table, t.table, sizeof(table));
turn = t.turn;
}
/**
* 可以填充空白
* @param x
* @param y
* @return
*/
bool can_fill_gap(int x, int y)
{
if (table[x][y] != 0)
return false;
else if (table[x][y - 1] == 0 || (table[x][y - 1]) % 10 == 7) // x7 has no successor
return false;
else
return true;
}
/**
* 填充空白
* @param x
* @param y
*/
void fill_gap(int x, int y)
{
int s, sx, sy;
sx = sy = -1;
s = table[x][y - 1] + 1;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 8; j++)
{
if (table[i][j] == s)
{
sx = i;
sy = j;
}
}
}
table[x][y] = table[sx][sy];
table[sx][sy] = 0;
turn++;
}
/**
* 是否是游戏结束状态，即每行都是升序，最后一列全为0
* @return
*/
bool done()
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 7; j++)
{
if (table[i][j] != (10 * (i + 1) + (j + 1)))
return false;
}
if (table[i][7] != 0)
return false;
}
return true;
}
bool operator==(const State &s) const
{
int i, j;
for (i = 0; i < 4; i++)
{
for (j = 1; j < 8; j++)
{
if (table[i][j] != s.table[i][j])
return false;
}
}
return true;
}
};
struct StateHash
{
size_t operator()(const State &s) const
{
size_t hash = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 1; j < 8; j++)
{
hash += s.table[i][j];
hash <<= 1;
}
}
return hash;
}
};
int solve(int card[4][7])
{
queue<State> que;
unordered_set<State, StateHash> visited;
//准备BFS
bool end = false;
int ans = INT_MAX;
State init(card);
if (init.done())
return 0;
que.push(init);
visited.insert(init);
//BFS
while (!que.empty() && !end)
{
State s = que.front();
que.pop();
for (int i = 0; i < 4; i++)
{
for (int j = 1; j < 8; j++)
{
if (s.can_fill_gap(i, j))
{
State temp(s);
temp.fill_gap(i, j);
// 结束
if (temp.done())
{
end = true;
ans = temp.turn;
}// 未遍历
else if (visited.find(temp) == visited.end())
{
que.push(temp);
visited.insert(temp);
}
}
}
}
}
if (ans == INT_MAX)
ans = -1;
return ans;
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int card[4][7];
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 7; ++j)
{
scanf("%d", &card[i][j]);
}
}
printf("%d\n", solve(card));
}
return 0;
}
