求一个遍历算法

Question

如图，有一8*8的方格，要求从任一点出发，到达不同色的另一个随机格。
　　要求：1.必须经过所有的64格；
　　2.每个方格只能经过一次。

Answer 1

边标记：
 X方向： X11...X99
 Y方向： Y11...Y99二维数组  XY[1..9][1..9]移动：  X 或者 Y 方向加或者减1  如果无法通过 X 或者 Y 方向加减一到达下一个未标记点，且已经标记数少于64，则失败

Answer 2

#include <stdio.h>   
#define N 100   
#define n 6   
int main()   
{   
    int dx[8],dy[8];   
    dx[0]=  2 , dy[0]= -1 ;   
    dx[1]=  1 , dy[1]= -2 ;   
    dx[2]= -1 , dy[2]= -2 ;   
    dx[3]= -2 , dy[3]= -1 ;   
    dx[4]= -2 , dy[4]=  1 ;   
    dx[5]= -1 , dy[5]=  2 ;   
    dx[6]=  1 , dy[6]=  2 ;   
    dx[7]=  2 , dy[7]=  1 ;   
    printf("********************\n");   
    for(int e=0;e<n;e++)   
        for(int r=0;r<n;r++)   
        {   
            int flag[N][N]={0};   
            int x[N],y[N],log[N]={0};   
            int beginx=e,beginy=r;   
            flag[beginx][beginy]=1;   
            int stepx=beginx,stepy=beginy;   
            x[0]=beginx,y[0]=beginy;   
            int t=1;   
            int sum=1;   
            while(t>0)   
            {   
                while(1)   
                {   
                    if(log[t]==8)      
                    {   
                        log[t]=0;   
                        goto L1;   
                    }   
                    stepx=stepx+dx[log[t]];   
                    stepy=stepy+dy[log[t]];   
                    if(stepx>=n||stepy>=n||stepx<0||stepy<0)   
                    {   
                        stepx-=dx[log[t]];   
                        stepy-=dy[log[t]];   
                        log[t]++;   
                        goto L0;
                    }          
                    if(flag[stepx][stepy]==1)   
                    {   
                        stepx-=dx[log[t]];   
                        stepy-=dy[log[t]];   
                        log[t]++;   
                    }   
                    if(flag[stepx][stepy]==0)   
                    {   
                        flag[stepx][stepy]=1;   
                        sum++;   
                        x[t]=stepx;   
                        y[t]=stepy;   
                        break;   
                    }   
L0:;   
                }   
                if(sum==n*n)    goto write;   
                t++;   
                goto L2;   
L1:   
                //flag[x[t]][y[t]]=0;   
                t--;   
                flag[x[t]][y[t]]=0;   
                sum--;   
                stepx=stepx-dx[log[t]];   
                stepy=stepy-dy[log[t]];   
                log[t]++;   
L2:;   
            }   
            goto out;   
write:   
            printf("\nbeginx=%d,beginy=%d\n",e,r);    
out:;   
        }   
    return 0;   
} 

Answer 3

是说先考虑对于颜色相同的两个格子A和B，以A为起点B为终点进行全遍历吗？呵呵这是不可能做到的。
因为整个棋盘中红色和绿色的格子数量是相等的，而且每一步只能从红色跳到绿色，或者从绿色跳到红色，所以，如果一条路径以红色开头红色结尾的话，整个路径中红色格子就会比绿色格子多一个，这就说明要么棋盘中某一个绿色格子没有走到，要么有某一个红色格子走了不止一遍。同样的，也不可能出现由绿色开头绿色结尾的遍历路径。

Answer 4

是说先考虑对于颜色相同的两个格子A和B，以A为起点B为终点进行全遍历吗？呵呵这是不可能做到的。
因为整个棋盘中红色和绿色的格子数量是相等的，而且每一步只能从红色跳到绿色，或者从绿色跳到红色，所以，如果一条路径以红色开头红色结尾的话，整个路径中红色格子就会比绿色格子多一个，这就说明要么棋盘中某一个绿色格子没有走到，要么有某一个红色格子走了不止一遍。同样的，也不可能出现由绿色开头绿色结尾的遍历路径。

只要把最后的不同色格定在最后的同色格旁边就可以了。