白色 bre 想法 转移 cst 自己 string typedef hash
这种鲜明的玄学风格很明显就是十几年前的题目。
在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士, 且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为1,纵坐标相差为2或者横坐标相差为2,纵坐标相差为1的格子)移动到空位上。 给定一个初始的棋盘,怎样才能经过移动变成如下目标棋盘: 为了体现出骑士精神,他们必须以最少的步数完成任务。
第一行有一个正整数T,表示一共有N组数据。接下来有T个5×5的矩阵,0表示白色骑士,1表示黑色骑士,*表示空位。两组数据之间没有空行。
对于每组数据都输出一行。如果能在15步以内(包括15步)到达目标状态,则输出步数,否则输出-1。
2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100
7
-1
T<=10。
拿到这道题应该没有别的想法吧,于是我们直接开始往搜索去想。
由于步数最多只有15,所以最暴力的暴力的时间复杂度为O(T*25*815)。
如果用A*算法解决这道题,估价函数为不符合答案的格子个数,如果剩余步数小于这个值,那么这个状态一定不能在15步内走到答案。
复杂度似乎可以不用乘上25,所以理论时间复杂度上限为O(T*815)。
所以A*算法就是这么神奇地通过该题的,网络上题解有很多,小C就不再赘述。
都是玄学。
所以小C还是介绍一下自己的折半搜索做法吧。
从目标状态往前搜8步,用一个map把每个状态hash的答案存下来。
从每个起始状态往后搜7步,对于每个状态到map查找并更新答案。
理论时间复杂度O(25*88*log(state)+T*25*87*log(state))。
加一个判重的剪枝,可以跑得飞快。
map还可以用O(1)的,hash还可以动态维护。所以时间复杂度可以优化到O(88+T*87)。
而且每个状态不是满的8种转移方式,实际的时间复杂度远远小于上限。
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <map>
- #define ll unsigned long long
- using namespace std;
- typedef char matr[6][6];
- const int fx[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
- map <ll,int> mp;
- matr c,d;
- int cx,cy,dx,dy,ans,t;
- inline int read()
- {
- int n=0,f=1; char c=getchar();
- while (c<‘0‘ || c>‘9‘) {if(c==‘-‘)f=-1; c=getchar();}
- while (c>=‘0‘ && c<=‘9‘) {n=n*10+c-‘0‘; c=getchar();}
- return n*f;
- }
- ll geth(matr c,int x,int y)
- {
- ll h=0;
- register int i,j;
- for (i=1;i<=5;++i)
- for (j=1;j<=5;++j) h=h*2+c[i][j]-‘0‘;
- h=h*5+x-1; h=h*5+y-1;
- return h;
- }
- bool check(int x,int y) {return x<1||x>5||y<1||y>5;}
- void dfs1(int stp)
- {
- ll h=geth(c,cx,cy);
- if (mp[h]&&mp[h]<=stp) return;
- mp[h]=stp;
- if (stp>8) return;
- register int i,ncx,ncy;
- for (i=0;i<8;++i)
- {
- ncx=cx+fx[i][0];
- ncy=cy+fx[i][1];
- if (check(ncx,ncy)) continue;
- swap(c[cx][cy],c[ncx][ncy]);
- swap(cx,ncx); swap(cy,ncy);
- dfs1(stp+1);
- swap(cx,ncx); swap(cy,ncy);
- swap(c[cx][cy],c[ncx][ncy]);
- }
- }
- void dfs2(int stp)
- {
- ll h=geth(d,dx,dy);
- if (mp[h]) ans=min(ans,stp+mp[h]-2);
- if (stp>7) return;
- register int i,ndx,ndy;
- for (i=0;i<8;++i)
- {
- ndx=dx+fx[i][0];
- ndy=dy+fx[i][1];
- if (check(ndx,ndy)) continue;
- swap(d[dx][dy],d[ndx][ndy]);
- swap(dx,ndx); swap(dy,ndy);
- dfs2(stp+1);
- swap(dx,ndx); swap(dy,ndy);
- swap(d[dx][dy],d[ndx][ndy]);
- }
- }
- int main()
- {
- register int i,j;
- t=read();
- for (i=1;i<=5;++i)
- for (j=1;j<=5;++j)
- if (i<j||i==j&&i<=2) c[i][j]=‘1‘;
- else if (i>j||i==j&&i>=3) c[i][j]=‘0‘;
- cx=cy=3; dfs1(1);
- while (t--)
- {
- ans=16;
- for (i=1;i<=5;++i) scanf("%s",d[i]+1);
- for (i=1;i<=5;++i)
- {
- for (j=1;j<=5;++j)
- if (d[i][j]==‘*‘) {dx=i; dy=j; d[i][j]=‘0‘; break;}
- if (j<=5) break;
- }
- dfs2(1);
- printf("%d\n",ans==16?-1:ans);
- }
- }
不过仔细想想玄学题目并不只是十几年前的专利啊,比如FJOI的D2T2……
[BZOJ]1085 骑士精神(SCOI2005)
来源: http://www.bubuko.com/infodetail-2330487.html