HDU ACM 4255 A Famous Grid

A Famous Grid

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1562 Accepted Submission(s): 603


Problem Description Mr. B has recently discovered the grid named "spiral grid".
Construct the grid like the following figure. (The grid is actually infinite. The figure is only a small part of it.)


Considering traveling in it, you are free to any cell containing a composite number or 1, but traveling to any cell containing a prime number is disallowed. You can travel up, down, left or right, but not diagonally. Write a program to find the length of the shortest path between pairs of nonprime numbers, or report it's impossible.


Input Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.

Output For each test case, display its case number followed by the length of the shortest path or "impossible" (without quotes) in one line.

Sample Input

1 4
9 32
10 12

Sample Output

Case 1: 1
Case 2: 7
Case 3: impossible

Source Fudan Local Programming Contest 2012 今天收獲還算非常棒！下午獨立a了兩個稍微復雜點兒的搜索題。累的我肩旁脖子疼啊，晚上上完實驗課操場跑了好幾圈沒啥用，腰酸背疼啊 ！ 說說這個題，當時訓練賽的時候很明確知道怎麼做，但畢竟自己代碼能力不強，寫不出來干著急啊 ！從那天就很明確，做的題目太少，時間不能浪費在debug上。 這周就要省賽了~~心想上學期要開始acm 應該會比現在好的多，寫完博客還得掛網課 ，馬上網課就要結束了 ，一節還沒上過。好了~，把代碼放這了~~有問題大家交流~~

#include
#include
#include
using namespace std;

const int  M=110;       //  設定一個全局常量非常方便
int cnt[M][M];
int primer[M*M];
int vis[M][M];
int s,e,t=0;
int dir[][2]= {{0,1},{1,0},{-1,0},{0,-1}};//控制四個方向

struct node
{
    int x,y,step;
};

void prime()           //  打印素數表
{
    memset(primer,0,sizeof(primer));
    for(int i=2; i<=M; i++)
    {
        if(!primer[i])
            for(int j=i*i; j<=M*M; j+=i)
            {
                primer[j]=1;
            }
    }
    primer[1]=1;
}

void inti()                 //初始化方格，把素數全都置為0，非素數按值存儲
{

    memset(cnt,0,sizeof(cnt));
    int tot=M*M;
    int x,y;
    x=0;
    y=0;
    cnt[0][0]=tot;
    while(tot>1)
    {

        while(y+1=0&&!cnt[x][y-1])
        {
            if(!primer[--tot])
            {
                cnt[x][--y]=0;
            }
            else
            {
                y--;
                cnt[x][y]=tot;
            }
        }

        while(x-1>=0&&!cnt[x-1][y])
        {

            if(!primer[--tot])
            {
                cnt[--x][y]=0;
            }
            else
            {
                x--;
                cnt[x][y]=tot;
            }
        }

    }
}


void bfs(int x,int y)   
{
    queuedict;
    node cur,next;
    cur.x=x;
    cur.y=y;
    cur.step=0;
    dict.push(cur);
    memset(vis,0,sizeof(vis)); // 初始化vis；
    vis[x][y]=1;                 //第一個點標記已經訪問過。
    int ok=1;

    while(!dict.empty())
    {
        cur=dict.front();
        dict.pop();               //調bug時發現拉下一次這個，結果導致無限循環
        for(int i=0; i<4; i++)
        {
            int tx=cur.x+dir[i][0];
            int ty=cur.y+dir[i][1];
            if(tx>=0&&ty>=0&&tx