付翔的专栏
在鄙视中成长 记录成长的点滴
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 付翔 阅读(242) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



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

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜