【题解】vijos P1029 晴天小猪历险记之number(bfs 康托展开)

显然这道题可以用bfs解决。我们可以首先得到8种横竖斜之和均为15的情况，然后给它们赋予一个值，从这八种情况扩展，开一个dis数组记录某种情况所需要的步数，然后扩展出哪种就给哪种步数+1就行了。但关键是dis数组的范围，倘若按照从数字编号，dis是肯定存不下的。我们注意到9个数的全排列是9！种，362200种可能，这个数还是比较小的，所以我们可以考虑把情况压缩成这种状态，但如何操作呢？这里就要用到康托展开（附上链接：https://blog.csdn.net/wbin233/article/details/72998375）。通过这种方法我们可以解决这个问题。注意有几个小技巧，往队列里添加初始的八种状态时可以让它们的step=1，然后判重时如果dis为0就添加到队列里去，这样可以省去bool类型的判重数组，最后答案减去1就可以了，同样也解决了不存在答案输出-1的情况。

#include
#include
#include
#include
#include
using namespace std;
const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
struct node
{int map[4][4];int step;
}team[4000000];
int dis[4000000];
int s,t;
int getnum(int map[4][4])
{int num=0;for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){num=num*10+map[i][j];}}return num;
}
int change(int x)
{bool b[10]={0};int ans=0;int p=8;while(x){int cnt=0;int tmp=x%10;for(int i=1;i=1;i--){for(int j=3;j>=1;j--){team[t].map[i][j]=x%10;x/=10;}}team[t].step=step;
}
void bfs()
{while(s!=t){s++;node now=team[s];
//		cout<>c;num=num*10+c;}printf("%d\n",dis[change(num)]-1);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！