poj 1014 多重背包

poj 3126 第一个BFS题

scturtle posted @ 2010年5月22日 07:44 in algorithm , 2407 阅读

Source Code

Problem: 3126   User: scturtle
Memory: 776K   Time: 16MS
Language: G++   Result: Accepted
  • Source Code
    #include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    #define MAX 9999
    int prime[MAX+1];
    int visit[MAX+1];
    int st,ed;
    int bas[4]= {1,10,100,1000};
    void shai()
    {
        for(int i=2; i<=MAX; ++i) prime[i]=1;
        int t;
        for(int i=2; i<=MAX/2; ++i)
        {
            t=2*i;
            while(t<=MAX)
            {
                prime[t]=0;
                t+=i;
            }
        }
    }
    
    void bfs()
    {
        fill(visit,visit+9999,0);
        queue<int> q;
        queue<int> qs;
        int t,ts;
        int n,ns;
        ts=0;
        t=st;
        q.push(t);visit[t]=1;
        qs.push(ts);
        int num,i,j;
        while(1)
        {
            t=q.front();q.pop();
            ts=qs.front();qs.pop();
            if(t==ed)
            {
                cout<<ts<<endl;
                return;
            }
            for(i=0; i<4; ++i)
                for(j=0; j<10; ++j)
                {
                    if(i==3&&j==0) continue;
                    num=t/bas[i]%10;
                    if(num!=j)
                    {
                        n=t-num*bas[i]+j*bas[i];
                        ns=ts+1;
                        if(!visit[n]&&prime[n]) {q.push(n);visit[n]=1;qs.push(ns);}
                    }
                }
        }
    
    }
    int main()
    {
        shai();
        int cas;
        cin>>cas;
        while(cas--)
        {
            cin>>st>>ed;
            bfs();
        }
    }
    

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter