HDU 4255 A Famous Grid

解题思路：广度优先搜索恶心题。题目考查知识不难，都是一些裸算法。只是题目操作有点繁杂，还有意想不到的边界条件，弄得题目有点恶心。

一个特殊的数表中（见题图），给出两个数字，求这两个数字之间的最短搜索距离（可以走四个方向）。但是，搜索过程中，不能经过内容为素数的点。

打表，搜索，小心素数，小心边界。

题目说x,y是在[1,10000]中，很多孩子就直接开了100X100的数组，把10000以内的数的表打出来。当然，包括纯洁的我。其实虽然是最大值是10000，但是，要是给出最外面的那一圈的数的话，我们的数表只打到这一圈，只能往里搜，就造成大拿错误。

首先，用筛选法求出素数的哈希表

然后，用搜索法打表（用到素数哈希表）

最后，输入数据后直接搜索就好了

不需要剪枝，不会超时！

 

#include
    
     #include
     
      #include
      
       using namespace std;int map[200][200];   //存储数表int flag[200][200];  //访问标记int pri[40002];  //素数哈希表int x,y;int sx,sy;int dir[4][2]={0,1,1,0,-1,0,0,-1};  //搜索方向struct node   //搜素节点{    int x;    int y;    int step;}s,e;void prime()   //筛选法求素数（哈希表存储，1表示非素数，0表示是素数）{    int i,j;    memset(pri,0,sizeof(pri));    for(i=2;i<=2000;i++)    for(j=i*2;j<=40000;j+=i)    pri[j]=1;    pri[1]=1;  //题目注明，1这个位置是可行的，视为非素数处理}void inital()   //形成表格（数表打表）{    int n=40000;  //数表赋值，搜索结束标志    int i,j;    memset(map,-1,sizeof(map));   //数表初始化（处理完后，素数出现的地方是-1，搜索时直接剪枝）    memset(flag,0,sizeof(flag));    s.x=0;    s.y=0;    map[0][0]=n--;    flag[0][0]=1;  //访问标记    while(1)  //一直搜索到n变成0    {        for(i=0;i<4;i++)        {            e.x=s.x+dir[i][0];  //下一处位置            e.y=s.y+dir[i][1];            if(e.x>=200||e.x<0||e.y>=200||e.y<0||flag[e.x][e.y])continue;  //该处补课操作            if(pri[n])map[e.x][e.y]=n;  //若该处出现的不是素数，数表赋值            n--;            flag[e.x][e.y]=1;  //访问标记            if(n<=0)break;            s.x=e.x;            s.y=e.y;            while(1)   //该路可走，要一直走到头（不撞南墙不转头）            {                e.x=s.x+dir[i][0];  //下一处处理位置（直走）                e.y=s.y+dir[i][1];                if(e.x>=200||e.x<0||e.y>=200||e.y<0||flag[e.x][e.y])break;  //该处不可操作                flag[e.x][e.y]=1;  //访问标记                if(pri[n])map[e.x][e.y]=n;  //若该处出现的不是素数，数表赋值                n--;                if(n<=0)break;                s.x=e.x;                s.y=e.y;            }            if(e.x>=200||e.x<0||e.y>=200||e.y<0,flag[e.x][e.y])break;        }        if(n<=0)break;    }}int bfs()  //搜索函数（常规广度优先搜索），从X搜Y，搜到则结束并返回步数，否则返回-1{    int i,j;    queue
       
         q;    s.x=sx;    s.y=sy;    s.step=0;    q.push(s);    memset(flag,0,sizeof(flag));    flag[sx][sy]=1;    while(!q.empty())    {        s=q.front();        q.pop();        for(i=0;i<4;i++)        {            e.x=s.x+dir[i][0];            e.y=s.y+dir[i][1];            e.step=s.step+1;            if(e.x>=200||e.x<0||e.y>=200||e.x<0||flag[e.x][e.y]||map[e.x][e.y]==-1)continue;            if(map[e.x][e.y]==y)  //搜到y了，搜索成功                return e.step;            flag[e.x][e.y]=1;            q.push(e);        }    }    return -1;  //能搜的地方都搜完了，没搜到y，搜素失败}int main(){    int i,j,k=1;    prime();  //筛选素数    inital();  //数表形成    while(cin>>x>>y)    {        for(i=0;i<200;i++)        for(j=0;j<200;j++)            if(map[i][j]==x)  //起点检索            {                sx=i,sy=j;                goto end;            }end:;        cout<<"Case "<
        
         <<": ";        int ans=bfs();  //搜索情况        if(ans==-1)cout<<"impossible"<