179. 八数码
给定 n 个正整数,将它们分组,使得每组中任意两个数互质。
至少要分成多少个组?
在一个 3×3 的网格中,1∼8这 8 个数字和一个 X
恰好不重不漏地分布在这 3×3的网格中。
例如:
1 2 3
X 4 6
7 5 8
在游戏过程中,可以把 X
与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 X
例如,示例中图形就可以通过让 X
先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把 X
与上下左右方向数字交换的行动记录为 u
、d
、l
、r
。
现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。
输入格式
输入占一行,将 3×3的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3
x 4 6
7 5 8
则输入为:1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个字符串,表示得到正确排列的完整行动记录。
如果答案不唯一,输出任意一种合法方案即可。
如果不存在解决方案,则输出 unsolvable
。
输入样例:
2 3 4 1 5 x 7 6 8
输出样例
ullddrurdllurdruldr
解析 : 题目求的是路径操作,对于通常的bfs,如果没有搜到合法方案的话,bfs就要把所有的状态都要遍历一遍 9^9=387420489,即使能搜到合法状态,但是由于是一层一层搜,搜索量依旧很大,这题时间卡掉了这种做法。有没有好的搜索方法,A*算法就能很好的解决这种情况,它能把搜索范围迅速缩小。只要搜很小的一部分就能得到最优解。下面是A*算法的伪代码。
A*有点类似Dijkstra,它有两个 参数一个是 d[i] 表示从起点到当前点的距离 , 另外一个是 f[i] 表示当前点到终点的估价距离 <= 真实距离g[i]。
A* while(!heap.empty()) { t <- 优先队列的队头 当终点第一次出队的时候 break; for t 所有的邻边 邻边入队 }
d[u]+f[u]<=d[u]+g[u]
如何保证第一次出队的终点就是最优解
证明: 假设u为最优路径上的一个点,至少起点是,假设终点出队时不是最优解,那么 dist > 最优解d >= d[u]+f[u];
如果不是最优解,那么队列中应该存在 一个点u使得 d[u]+f[u]<= 最优解d,此时就违反优先队列的规则了,最小的元素应该先出队,而现在却找到了比队头更小的元素,因此矛盾了。
//上面这个y总在提高课里讲的证明,但我感觉有问题,不是很懂的亚子。 #include<cstring>
#include<iostream> #include<algorithm> #include<unordered_map> #include<queue> #define x first #define y second using namespace std; typedef pair<int,string> PIS; const int N=9; int f(string state) //估价函数 算的是曼哈顿距离,即x,y 分别差值的绝对值之和 { int res=0; for(int i=0;i<state.size();++i) { if(state[i]!='x') { int t=state[i]-'1'; res+=abs(t/3-i/3)+abs(t%3-i%3); } } return res; } string astar(string start) { unordered_map<string,int> dist; unordered_map<string, pair<string,char>> prev; //保存前一个状态,和操作 priority_queue<PIS,vector<PIS>,greater<PIS>>heap; //堆 heap.push({f(start),start}); string end={"12345678x"}; char op[4]={'u','d','l','r'}; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; while(heap.size()) { auto t=heap.top(); heap.pop(); string state=t.y; if(state==end) break; int x,y; for(int i=0; i<state.size(); ++i) { if(state[i]=='x') { x=i/3,y=i%3; break; } } string source=state; for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=3 || b<0 || b>=3) continue; swap(state[a*3+b],state[3*x+y]); if(!dist.count(state) || dist[state]>dist[source]+1) { dist[state]=dist[source]+1; prev[state]={source,op[i]}; heap.push({dist[state]+f(state),state}); } swap(state[a*3+b],state[3*x+y]); } } string res; while(end!=start) { res+=prev[end].y; end=prev[end].x; } reverse(res.begin(),res.end()); //取反,原因res加入的时候,是倒着加入的所以,最终的结果是反着来的,也就是从终点到起点,而我们求的是起点到终点 return res; } int main() { string start,seq; char c; for(int i=0;i<=8;++i) { cin>>c; start+=c; if(c!='x') seq+=c; } int cnt=0; //逆序数,12345678x,
//123
//456
//78x 某个数只有上下的移动才会改变逆序数,左右移动是不改变的,改变的逆序数只有+2,或者是-2,逆序数的数量一定是偶数,所以奇数的情况就是无解。
for(int i=0;i<8;++i) for(int j=i;j<8;++j) if(seq[i]>seq[j]) cnt++; if(cnt&1) printf("unsolvable"); else cout<<astar(start); return(0); }