//2012年多校联合赛  A Famous Grid
//题目大意:输入两个数,在网格中找到这两个数的位置,并找一条连通两个点的最短路径,路径要求,不可以经过素数网格(即所填数字为素数
//的网格)
//题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4255
#include <stdio.h>

#include <math.h>
#include <string.h>

#define N 40000
#define M 200

bool prime[N],vis[M][M];
int min;
int index[N],map[M][M],dis[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//dis数组为四个方向
int queue[N],d[M][M],rear,front;

//打印素数表
void isPrime(){
    int i,j;
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(i=0;i<N;i++)
        if(prime[i]){
            for(j=i*i;j<N;j+=i)
                prime[j]=false;
        }
}

//打印填有数字的网格
void init(){
    int i,n=M*M,k=M,ii,jj;
    isPrime();
    for(i=0;k;k-=2,i++){
        for(ii=jj=0;jj<k;jj++){
            index[n]=(ii+i)*M+jj+i;
            map[ii+i][jj+i]=n–;    
        }
        for(ii++,jj–;ii<=jj;ii++){
            index[n]=(ii+i)*M+jj+i;
            map[ii+i][jj+i]=n–;
        }
        for(ii–,jj–;jj>=0;jj–){
            index[n]=(ii+i)*M+jj+i;
            map[ii+i][jj+i]=n–;
        }
        for(jj++,ii–;ii>0;ii–){
            index[n]=(ii+i)*M+jj+i;
            map[ii+i][jj+i]=n–;
        }
    }
}

//广搜最短路径
//原先不知道该怎样存储这个路径长度,怎样才能保证每一层的长度是上一层的长度+1,所以就用到类似于DP的状态转移
void bfs(int e){
    int i,x,y,t,sum=0;
    memset(d,0,sizeof(d));
    while(front<rear){
        t=queue[front++];
        if(t==e)
            break;
        for(i=0;i<4;i++){
            x=t/M+dis[i][0];
            y=t%M+dis[i][1];
            if(x>=0 && x<M && y>=0 && y<M && vis[x][y]==false && (prime[map[x][y]]==false || x*M+y==e)){
                vis[x][y]=true;
                queue[rear++]=x*M+y;
                d[x][y]=d[t/M][t%M]+1;//每一层的长度是上一层的长度+1
            }
        }
    }
    if(front<rear)
        min=d[t/M][t%M];
}

int main(){
    int x,y,t=1;
    init();
    while(scanf(“%d%d”,&x,&y)!=EOF){
        min=0x7fffffff;
        memset(vis,false,sizeof(vis));
        front=rear=0;
        vis[index[x]/M][index[x]%M]=true;
        queue[rear++]=index[x];
        bfs(index[y]);
        printf(“Case %d: “,t++);
        if(min==0x7fffffff)
            printf(“impossible\n”);
        else
            printf(“%d\n”,min);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation