/* *骑士巡游 能否不重复走慢整个棋盘 数据结构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; } /* 这个程序 最开始是一口气写完 但是运行就发现有很多错误 改的时间也很多 也许是很久没有写程序的缘故吧 */