• <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 - 106,  comments - 32,  trackbacks - 0
            /*
             *騎士巡游 能否不重復走慢整個棋盤 數據結構P63
             *algorithm :騎士總是移向出口最少且沒有到達的方塊
             * 試做用類來做
             * author:fuxiang
            */

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

            using namespace std;
            const int row = 8,col = 8;
            int kmovex[8= {-2,-1,1,2,2,1,-1,-2};
            int kmovey[8= {1,2,2,1,-1,-2,-2,-1};
            class Knight
            {
            public:
                
            //const int row = 8,col = 8;
                Knight(){startx=0,starty=0;}
                Knight(
            int x,int y){startx = x;starty=y;}
                
            void output()
                
            {
                    
            int i,j;
                    process();
                    
            for(i = 0; i < step;i++)
                        printf(
            "step %d : %d %d \n",i,path[i][0],path[i][1]);

                    
            for(i = 0;i<step;i++)
                        kmap[path[i][
            1]][path[i][0]] = i;
                    printf(
            "map of knight \n");
                    
            for(i=0;i<8;i++)
                    
            {
                        
            for(j=0;j<8;j++)
                            printf(
            "%02d ",kmap[i][j]);
                        printf(
            "\n");
                    }

                    printf(
            "kcanmove array is :\n");
                    
            for(i=0;i<8;i++)
                    
            {
                        
            for(j=0;j<8;j++)
                            printf(
            "%02d ",kcanmove[i][j]);
                        printf(
            "\n");
                    }

                }

            private:

                
            int startx,starty,step ;
                
            int visted[row][col];
                
            int kcanmove[row][col];//記錄當前位置可以走的方向
                int kmap[row][col];
                
            int path[row*col][2];
                
            bool check(int x,int y)
                
            {
                    
            if(x>=0  && x < 8 && y >=0 && y < 8)
                        
            return true;
                    
            return false;
                }

                
            int CountKnightCanMove(int x,int y)
                
            {
                    
            int c = 0,i;
                    
            for(i =0;i < 8;i++)
                        
            if(check(x+ kmovex[i],y + kmovey[i]) && visted[x+ kmovex[i] ][ y + kmovey[i] ] == 0) c ++;
                    
            return c;
                }

                
            /*是用來找出周圍可走步數中 具有最小的步數的下一步 這個函數是寫的最爛的 當然整個程序也不咋的
                
            */

                
            int FindMinOut(int x,int y)
                
            {
                    
            int i,min = -1,flag = 0;
                    
            for(i = 0;i < 8;i++)
                    
            {
                        
            if(visted[x+ kmovex[i]][y + kmovey[i]]!= 0 || kcanmove[x+ kmovex[i] ][ y + kmovey[i]] <= 0)
                            
            continue;
                        
            if(flag == 0
                        
            {
                            
            if(check(x+ kmovex[i],y + kmovey[i]) && visted[x+ kmovex[i]][y + kmovey[i]]==0)//找到第一個符合條件的
                                min = i,flag = 1;
                        }

                        
            else if(kcanmove[x+ kmovex[i] ][ y + kmovey[i] ] <= kcanmove[x+ kmovex[min]][ y + kmovey[min]]
                            
            && check(x+ kmovex[i],y + kmovey[i]) && visted[x+ kmovex[i]][y + kmovey[i]]==0)
                            min 
            = i;
                        
            //if(check(x+ kmovex[i+1],y + kmovey[i+1]) && visted[x+ kmovex[i+1]][y + kmovey[i+1]]==0)
                        
            //    min = i+1;
                    }

                    
            return min;
                }

                
            void init()
                
            {
                    step 
            = 0;
                    
            int i,j;
                    
            //visted[startx][starty] = 1; //放在這里 貌似沒有改變他的值

                    memset(kmap,
            0,sizeof(kmap));
                    memset(visted,
            0,sizeof(visted));
                    memset(path,
            0,sizeof(path));
                    
            for(i = 0; i < 8;i++)
                        
            for(j = 0 ; j < 8;j++)
                            kcanmove[i][j] 
            = CountKnightCanMove(i,j);
                
                }

                
            void process()
                
            {
                    
            int npos = 8;
                    
            int nextstep,curx,cury,tx,ty;
                    init();
                    visted[startx][starty] 
            = 1;//放在這里就好了
                    path[step][0= startx,path[step][1= starty;
                    
            for(step =1;step < 64;step ++)
                    
            {
                        curx 
            = path[step-1][0];
                        cury 
            = path[step-1][1];
                        nextstep 
            = FindMinOut(curx,cury);

            //             for(nextstep = 0; nextstep<8;nextstep++)
            //                 if(check(curx+kmovex[nextstep],cury + kmovey[nextstep]) &&
            //                     visted[curx+kmovex[nextstep]][cury + kmovey[nextstep]] == 0)
            //                     break;
                        if(nextstep == -1 || nextstep == 8 ) {printf("Knight is over\n");break;}
                         curx 
            += kmovex[nextstep];cury += kmovey[nextstep];
                        visted[curx][cury] 
            = 1;//標記為已經走過
                        
            //kcanmove[curx][cury] = -1;//為不可達
                        path[step][0= curx;
                        path[step][
            1= cury;

                        
            //更新
                        for(int i = 0; i < 8; i ++)
                        
            {
                            tx 
            = curx + kmovex[i];
                            ty 
            = cury + kmovey[i];
                            
            if(check(tx,ty) == falsecontinue;
                            kcanmove[tx][ty] 
            --;
                            
            if(kcanmove[tx][ty] <  0)
                                kcanmove[tx][ty] 
            = 0;
                            
            //CountKnightCanMove(curx + kmovex[nextstep]+kmovex[i],cury + kmovey[nextstep]+kmovey[i]);
                        }


                    }


                }




            }
            ;
            int main()
            {
                
            int x,y;
                scanf(
            "%d%d",&x,&y);
                Knight knight(x,y);
                knight.output();
                
            return 0;
            }

            /*
            這個程序 最開始是一口氣寫完 但是運行就發現有很多錯誤 改的時間也很多 也許是很久沒有寫程序的緣故吧

            */
            posted on 2011-02-09 16:05 付翔 閱讀(280) 評論(0)  編輯 收藏 引用 所屬分類: ACM 數據結構

            <2011年2月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272812345
            6789101112

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            一本久久a久久精品亚洲| 2021久久精品国产99国产精品| 色欲av伊人久久大香线蕉影院| 久久精品免费大片国产大片| 久久久久国产精品熟女影院| 国产亚洲精午夜久久久久久 | 久久国产AVJUST麻豆| 久久久久久av无码免费看大片| 欧美精品一本久久男人的天堂| 青青青伊人色综合久久| 久久这里只精品国产99热| 久久伊人精品青青草原高清| 精品国产婷婷久久久| 日韩亚洲国产综合久久久| 亚洲精品无码久久久久AV麻豆| 亚洲一级Av无码毛片久久精品| 久久精品国产99国产精品亚洲| 99久久国产宗和精品1上映 | 久久综合亚洲欧美成人| 亚洲欧美伊人久久综合一区二区| 亚洲精品乱码久久久久久中文字幕 | 久久精品无码一区二区三区日韩 | 久久国产精品波多野结衣AV| 久久无码国产| 亚洲国产欧洲综合997久久| 久久久久久a亚洲欧洲aⅴ| 欧美精品一区二区久久| 无码人妻久久一区二区三区免费丨 | 亚洲精品无码久久久久去q| 久久99精品国产| 99精品国产免费久久久久久下载 | 久久久亚洲欧洲日产国码是AV| 色诱久久久久综合网ywww| 国产成人综合久久久久久| 2021国产精品久久精品| 久久91亚洲人成电影网站| 无码任你躁久久久久久老妇| 国产精品久久久亚洲| 亚洲欧洲久久av| 国产精品永久久久久久久久久| 97精品依人久久久大香线蕉97|