最近昀昀学习到了一种新的棋盘游戏，这是一个在一个N×N的格子棋盘上去搞M个棋子的游戏，游戏的规则有下列几条：
- 棋盘上有且仅有一个出口
- 开始时没有哪个棋子在出口，而且所有棋子都不相邻（这里的相邻是指上下左右四个方向）
- M个棋子分别记为1到M
- 每个时刻你可以移动一个棋子向它相邻的四个格子移动一步
- 你需要保证任意时刻棋盘上所有棋子都不相邻
- 只有当前棋盘上编号最小的棋子移动到出口时才能取走改棋子。
- 所有棋子都移走的时候游戏结束
对于一个给定的游戏局面，昀昀最少要多少步才能结束这个游戏呢？
Input
第一行有一个整数T，(T≤200)，表示测试数据的组数。
对于每一组数据，第一行是两个整数N,M，其中2≤N≤6, 1≤M≤4。
接下来是一个N×N的棋盘，其中o代表空格子，x代表出口,其余的1到M代表这M个棋子。
保证数据是合法的。
Output
对于每一组数据输出最少步数，如果无解输出−1。
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 |
7 |
解题报告
自己也是太年轻。。以为是道大水题，直接上bfs爆搜，果断TLE。。
略思考后显然是A*算法（大水题。。。曼哈顿距离呐）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue> using namespace std; const int Max= ;
int N,M,tid,ttx,tty;
char G[Max][Max];
bool vis[][][][]; typedef struct status{
int pos[],step,pol,f;
friend bool operator < (status a,status b)
{
if (a.step + a.f < b.step + b.f) return false;
if (a.step + a.f > b.step + b.f) return true;
if (a.step < b.step) return false;
else
return true;
}
}; priority_queue<status>q;
status start;
int pol;
int dir[][] = {,,,-,,,-,}; /*A* */
int caculatef(status& x){
int result = ;
for(int i = ;i<M;++i)
result += (abs(x.pos[i] / N - ttx) + abs(x.pos[i] % N - tty) );
return result;
} bool judge(status &x){
for(int i = x.pol;i < M;++i)
for(int j = i;j < M;++j)
if (i != j)
{
int tx1 = x.pos[i] / N;
int ty1 = x.pos[i] % N;
int tx2 = x.pos[j] / N;
int ty2 = x.pos[j] % N;
if (tx1 == tx2 && abs(ty1 - ty2) == ) return false;
else if(ty1 == ty2 && abs(tx1-tx2) == ) return false;
else if(tx1 == tx2 && ty1 == ty2) return false;
}
return true;
} int bfs(){
memset(vis,false,sizeof(vis));
vis[start.pos[]][start.pos[]][start.pos[]][start.pos[]] = true;
start.step = ;
q.push(start);
while(!q.empty())
{
status temp = q.top();q.pop();
if(temp.pos[temp.pol] == tid)
temp.pol++;
if (temp.pol == M) return temp.step;
for(int i = temp.pol;i<M;++i)
for(int j = ;j<;++j)
{
int newx = temp.pos[i] / N + dir[j][];
int newy = temp.pos[i] % N + dir[j][];
if (newx >= N || newx < || newy >= N || newy < ) continue;
int nid = newx * N + newy;
status nst = temp;
nst.pos[i] = nid;
if (!judge(nst)) continue;
if (vis[nst.pos[]][nst.pos[]][nst.pos[]][nst.pos[]] ) continue;
vis[nst.pos[]][nst.pos[]][nst.pos[]][nst.pos[]] = true;
nst.step = temp.step + ;
nst.f = caculatef(nst);
q.push(nst);
}
} return -;
} int main(int argc,char * argv[]){
int T;
scanf("%d",&T);
while(T--)
{
while(!q.empty())
q.pop();
for(int i = ;i<;++i)
start.pos[i] = ;
start.pol = ;
scanf("%d%d%*c",&N,&M);
for(int i = ;i<N;++i)
gets(G[i]);
for(int i = ;i<N;++i)
for(int j = ;j<N;++j)
if(G[i][j] <= '' && G[i][j] >='')
start.pos[G[i][j] - ''] = i*N+j;
else if(G[i][j] == 'x')
tid = i*N + j;
ttx = tid / N;
tty = tid % N;
start.f = caculatef(start);
cout << bfs() << endl;
}
return ;
}