程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU ACM 4255 A Famous Grid

HDU ACM 4255 A Famous Grid

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved