题目链接: 1077 -- Eight http://poj.org/problem?id=1077
题目要求:输入一个字符串(表示九宫格状态),要求输出其变成标准形式的移动步骤(u表示上,d表示下,l表示左,r表示右),无解则输出unsolvable
样例过了,也用了逆序数判无解的情况(也测试过可以),提交就出错了,但是就是不知道哪里出错了,看了好几遍自己的代码了,也不知道错在哪里,希望大家能帮我看看,感谢🙇。 代码如下
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
map<string,int>Map;
pair<string,string>p;
queue<string> q;
string str;
string mb = "12345678x";
bool check(string s){ //判断是否为目标
for(int i = 0; i < 9; i++){
if(s[i] != mb[i])return false;
}
return true;
}
bool unsolvable(string s){ //判断是否有解函数
int t = 0;
for(int i = 0; i < s.length() - 1; i++){
for(int j = i + 1; j < s.length(); j++){
if(s[i] == 'x' || s[j] == 'x')continue;
int a = s[i] - '0';
int b = s[j] - '0';
if(a > b)t++;
}
}
//cout << "t = " << t << endl;
if(t&1)return false;
return true;
}
bool bfs(string s){
string s1,s2;
q.push(s);
Map.insert(pair<string,int>(s,66));
while(!q.empty()){
s1 = q.front(); q.pop();
if(!unsolvable(s1))return false; //判断是有解
if(check(s1)){
string str1,str2;
char str3[1000];
int a = Map.find(s1)->second,b = 0;
str1 = Map.find(s1)->first;
while(a != 66 && a != 0){ //下面是通过map保存的字符串逆向回去,打印移动路径
int xx;
for(int i = 0; i < 9; i++){
if(str1[i] == 'x')xx = i;
}
if(a == -3){
str3[b++] = 'u';
str2 = str1;
str2[xx] = str1[xx+3];
str2[xx+3] = str1[xx];
}
if(a == -1){
str3[b++] = 'l';
str2 = str1;
str2[xx] = str1[xx+1];
str2[xx+1] = str1[xx];
}
if(a == 3){
str3[b++] = 'd';
str2 = str1;
str2[xx] = str1[xx-3];
str2[xx-3] = str1[xx];
}
if(a == 1){
str3[b++] = 'r';
str2 = str1;
str2[xx] = str1[xx-1];
str2[xx-1] = str1[xx];
}
str1 = str2;
a = Map.find(str2)->second;
}
for(int i = b - 1; i >= 0; i--)cout << str3[i];
return true;
}
int x;
for(int i = 0; i < 9; i++){ //定位x的位置 (x分四个方向进行移动,用一维数组模拟)
if(s1[i] == 'x')x = i;
}
//上
if(x - 3 >= 0){
s2 = s1;
s2[x-3] = s1[x];
s2[x] = s1[x-3];
if(Map.find(s2) == Map.end()){
Map.insert(pair<string,int>(s2,-3));
q.push(s2);
}
}
//左
if(x - 1 >= 0 && (x % 3) != 0){ //用一维数组模拟二维,(在二维中)当x在某一行的最左边就不能往左移了,下面类似
s2 = s1;
s2[x-1] = s1[x];
s2[x] = s1[x-1];
if(Map.find(s2) == Map.end()){
Map.insert(pair<string,int>(s2,-1));
q.push(s2);
}
}
//下
if(x + 3 < 9){
s2 = s1;
s2[x+3] = s1[x];
s2[x] = s1[x+3];
if(Map.find(s2) == Map.end()){
Map.insert(pair<string,int>(s2,3));
q.push(s2);
}
}
//右
if(x + 1 < 9 && ((x + 1) % 3) != 0){
s2 = s1;
s2[x+1] = s1[x];
s2[x] = s1[x+1];
if(Map.find(s2) == Map.end()){
Map.insert(pair<string,int>(s2,1));
q.push(s2);
}
}
}
return false;
}
int main(){
char c[9];
for(int i = 0; i < 9; i++)cin >> c[i];
str = c;
if(!bfs(str))cout << "unsolvable" << endl;
return 0;
}
是超时吗
定义估价函数h():为每个数或空格的位置 到 最终状态中所在位置 的 曼哈顿距离 的 总和。
把状态压成一个九进制数,便于存储和判重。
然后记录方案可以记录一下此次的操作和上一次的状态,具体见代码。
map比哈希快
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<algorithm>
#define R register int
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1},end=54480996;
const int py[]={0,1,2,0,1,2,0,1},px[]={0,0,0,1,1,1,2,2};
const char op[4]={'u','r','d','l'};
using namespace std;
inline int g() {
R ret=0; register char ch; while(!isdigit(ch=getchar()));
do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret;
}
struct node{ int sta,g,h; node() {}
node(int ss,int gg,int hh) {sta=ss,g=gg,h=hh;}
bool operator <(const node& y) const {return g+h>y.g+y.h;}
}; int a[3][3];
map<int,int> d,pre,dir;
priority_queue<node> q;
inline bool ckpos(int x,int y) {return x<0||x>2||y<0||y>2;}
inline int calc(int p[3][3]) { R ret=0;
for(R i=0;i<3;++i) for(R j=0;j<3;++j) ret=ret*9+p[i][j]; return ret;
}
inline pair<int,int> recalc(int vl,int p[3][3]) { R x,y;
for(R i=2;i>=0;--i) for(R j=2;j>=0;--j) {
p[i][j]=vl%9,vl/=9; if(p[i][j]==0) x=i,y=j;
} return make_pair(x,y);
}
inline int h(int p[3][3]) { R ret=0;
for(R i=0;i<3;++i) for(R j=0;j<3;++j) {
if(p[i][j]==0) continue;
ret+=abs(i-px[p[i][j]-1])+abs(j-py[p[i][j]-1]);
} return ret;
}
inline int Astar() {
d.clear(),pre.clear(),dir.clear();
while(q.size()) q.pop(); R st=calc(a); d[st]=0;
q.push(node(st,0,h(a)));
while(q.size()) {
node u=q.top(); R crt=q.top().sta; q.pop();
if(crt==end) return u.g;
R a[3][3]; register pair<int,int> blk=recalc(crt,a); R x=blk.first,y=blk.second;
for(R i=0;i<4;++i) { R xx=x+dx[i],yy=y+dy[i];
if(ckpos(xx,yy)) continue; swap(a[x][y],a[xx][yy]);
R nxt=calc(a); if(d.find(nxt)==d.end()||d[nxt]>d[crt]+1)
d[nxt]=d[crt]+1,pre[nxt]=crt,dir[nxt]=i,q.push(node(nxt,d[nxt],h(a)));//此处存了nxt的上一个状态和如何操作
swap(a[xx][yy],a[x][y]);
}
} return -1;
}
inline void print(int s) {
if(pre.find(s)==pre.end()) return;
print(pre[s]); putchar(op[dir[s]]);
}
signed main() {
for(R i=0;i<3;++i) for(R j=0;j<3;++j) { register char ch;
while(!isdigit(ch=getchar())&&ch!='x');
if(ch=='x') a[i][j]=0;
else a[i][j]=ch^48;
} R ans=Astar(); if(ans==-1) printf("unsolvable"),putchar('\n'); else print(end);
}