/**//*
*騎士巡游 能否不重復走慢整個棋盤 數據結構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) == false) continue;
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
付翔 閱讀(299)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構