• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 7, comments - 13, trackbacks - 0, articles - 37
               :: 首頁 :: 新隨筆 :: 聯(lián)系 ::  :: 管理

            #include <stdio.h>
            #include <stdlib.h>
            #include <string.h>

            const int hashsize=70001;
            const int maxnode=50000;
            const int maxp=40;
            const int ten[]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
            const int C[]={2,3,2,3,4,3,2,3,2};
            const int EP[][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}};

            struct Tlist
            {
             int data,d;
             Tlist *next;
            };
            struct Thashpoint
            {
             int data;
             Thashpoint *next;
            };
            //Memory
            int ID;
            Tlist listM[maxnode],*q;
            Thashpoint hashM[maxnode],*p;
            //data
            int src,dest;
            //heap
            Tlist *head[maxp],*expand[maxp],*lp1,*lp2;
            //Hash
            Thashpoint *hash[hashsize];
            //expand
            int nowp,A[9],arcT[9],dist[9][9],b,depth,swap[9][9];
            int data,G,newdata,newG;
            bool find_answer;

            void readdata(const char *filename,int &data)
            {
             int i,v;
             FILE *f=fopen(filename,"r");
             data=0;
             for (i=0;i<9;i++)
             {
              fscanf(f,"%d",&v);
              data=data+v*ten[i];
             }
             fclose(f);
            }
            bool check_noanswer()
            {
             int p[9],i,b1,b2;
             bool vis[9];
             for (i=0;i<9;i++)
              p[i]=arcT[src/ten[i]%10];
             for (b1=0; src/ten[b1]%10!=0;b1++);
             for (b2=0;dest/ten[b2]%10!=0;b2++);
             int countP=0;
             memset(vis,false,sizeof(vis));
             for (i=0;i<9;i++)
              if (!vis[i])
              {
               countP++;
               for (int k=i;!vis[k];k=p[k])
                vis[k]=true;
              }
             return (countP-dist[b1][b2])%2==0;
            }
            void preprocess()
            {
             ID=0;
             find_answer=false;
             memset(hash,0,sizeof(hash));
             memset(head,0,sizeof(head));
             memset(expand,0,sizeof(expand));
             for (int k=0;k<9;k++)
              arcT[dest/ten[k]%10]=k;
             for (int u=0;u<9;u++)
              for (int v=0;v<9;v++)
              {
               dist[u][v]=abs(u/3-v/3)+abs(u%3-v%3);
               swap[u][v]=ten[u]-ten[v];
              }
            }
            void addnode()
            {
             if (newdata==dest)
             {
              printf("%d\n",depth);
              find_answer=true;
              return;
             }
             int address=newdata%hashsize;
             for (p=hash[address];p!=NULL;p=p->next)
              if (p->data==newdata)
               return;
             if (ID==maxnode)
              return;
             p=&hashM[ID];
             p->data=newdata;
             p->next=hash[address];
             hash[address]=p;
             q=&listM[ID];
             ID++;
             q->data=newdata;
             q->d=depth;
             if (newG>=maxp)
              return;
             if (newG==nowp)
             {
              q->next=expand[depth];
              expand[depth]=q;
             }
             else
             {
              q->next=head[newG];
              head[newG]=q;
             }
            }
            void solve()
            {
             nowp=-1;
             newdata=src;
             newG=0;
             for (int k=0;k<9;k++)
              if (src/ten[k]%10!=0)
               newG+=dist[arcT[src/ten[k]%10]][k];
             depth=0;
             addnode();
             if (find_answer)
              return;
             for (int p=0;p<maxp;p++) if (head[p]!=NULL)
             {
              nowp=p;
              for (lp1=head[p];lp1!=NULL;lp1=lp2)
              {
               lp2=lp1->next;
               lp1->next=expand[lp1->d];
               expand[lp1->d]=lp1;
              }
              for (int d=0;d<=p;d++)
               for (;expand[d]!=NULL;)
               {
                data=expand[d]->data;
                G=p-expand[d]->d;
                depth=expand[d]->d+1;
                expand[d]->d=-2;
                expand[d]=expand[d]->next;
                for (b=0;data/ten[b]%10!=0;b++);
                for (int v=0;v<C[b];v++)
                {
                 int u=EP[b][v];
                 int c=data/ten[u]%10;
                 newdata=data+swap[b][u]*c;
                 c=arcT[c];
                 newG=depth+G-dist[c][u]+dist[c][b];
                 addnode();
                 if (find_answer)
                  return;
                }
               }
             }
             printf("-1\n");
            }
            int main()
            {
             readdata("start.txt",src);
             readdata("goal.txt",dest);
             preprocess();
             if (check_noanswer())
              printf("-1\n");
             else
              solve();
             return 0;
            }

             


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            亚洲AV无码久久| 欧美性大战久久久久久| 97r久久精品国产99国产精| 久久国产热精品波多野结衣AV| 久久99国产精品尤物| 精品国产乱码久久久久久浪潮| 日本精品久久久久影院日本| 香蕉久久av一区二区三区| 欧美亚洲另类久久综合| 久久天天躁夜夜躁狠狠躁2022| 久久精品国产亚洲AV无码娇色| 精品国产一区二区三区久久蜜臀| 亚洲国产精品无码久久久秋霞2| 91久久精品国产免费直播| 久久午夜福利无码1000合集| 久久青青草原国产精品免费| 久久伊人精品一区二区三区| 国产亚洲色婷婷久久99精品91| 人妻精品久久久久中文字幕69| 久久精品国产99久久香蕉| 色综合久久天天综合| 激情伊人五月天久久综合| 一本色道久久88综合日韩精品 | 久久99国产综合精品| 人妻中文久久久久| 国产精品免费久久| 久久精品一区二区国产| 久久www免费人成看片| 欧美亚洲另类久久综合婷婷| 一本一道久久精品综合| 久久精品国产精品青草app| 无码国内精品久久人妻| 97精品国产97久久久久久免费 | 久久青青草原国产精品免费| 一本一本久久a久久综合精品蜜桃| 亚洲国产成人久久精品99 | 伊人久久免费视频| 久久天堂电影网| yellow中文字幕久久网| 精品久久久久久久久久中文字幕 | 久久伊人色|