16.txt

骑士巡游问题

#include <stdio.h>
int qipan[11][11] ;   //棋盘数组
int way[121][121];  //所走棋格记录
int n,m;            //全局变量，后面主函数调用子函数要用到

void rec(int i1,int j1,int i2,int j2)
{
    way[(i1-1)*n+j1][(i2-1)*n+j2]=1;
    way[(i2-1)*n+j2][(i1-1)*n+j1]=1;
    return;          //在二维棋格记录中骑士所在位置置1
}

void makeqp()        //根据用户要求输入制作棋盘
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++) 
            qipan[i][j]=0;   //所用棋格都先置0
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++) 
            way[i][j]=0;     //把棋盘记录也都先置0

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(qipan[i][j]==0)
{
            qipan[i][j]=1;    //骑士所走的棋格都置1
            if((i+2<=n)&&(j+1<=n)) rec(i,j,i+2,j+1);
            if((i+2<=n)&&(j-1>=1)) rec(i,j,i+2,j-1);
            if((i-2>=1)&&(j+1<=n)) rec(i,j,i-2,j+1);
            if((i-2>=1)&&(j-1>=1)) rec(i,j,i-2,j-1);
            if((j+2<=n)&&(i+1<=n)) rec(i,j,i+1,j+2);
            if((j+2<=n)&&(i-1>=1)) rec(i,j,i-1,j+2);
            if((j-2>=1)&&(i+1<=n)) rec(i,j,i+1,j-2);
            if((j-2>=1)&&(i-1>=1)) rec(i,j,i-1,j-2);  //防止骑士走到棋格外的约束
}
    return;
}

void mov(int hang,int index)    //hang都是棋盘记录数组,index是用来判断可否移动的值，初始置0，因为棋盘移动与否是0与1的区别
{
    int i,j,ha;

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(qipan[i][j]>index) qipan[i][j]=0;//棋盘位置信息先清空
    index++;
    i=((hang-1)/n)+1;   
    j=((hang-1)%n)+1;         //把棋格记录中的位置给棋盘
	qipan[i][j]=index;      //此位置上置1
    for(ha=1;ha<=m;ha++)
    {
        i=((ha-1)/n)+1;
        j=((ha-1)%n)+1;
        if((way[hang][ha]==1)&&(qipan[i][j]==0)) mov(ha,index);//当移动允许时，递归使用
    }
    return;
}

void main()
{
    int i,j,index,l,flag,lable;
    printf("输入一个大于3的n,以制作一个n*n的棋盘,n:");scanf("%d",&n);
    m=n*n;
    makeqp();       //调用制作棋盘
    printf("输入起始位置,确定骑士从几行几列出发,行列间请用空格隔开,现在请输入:");
    scanf("%d %d",&i,&j);
    l=(i-1)*n+j;
    while ((i>0)||(j>0))
    {
        flag=1;
		for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        qipan[i][j]=0;    //棋盘先都置0
    index=0;
    mov(l,index);
	for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++) 
		printf("%4d",qipan[i][j]);
         printf("\n");   //输出最终的棋盘
    }
     for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++) 
		{
			if(qipan[i][j]==0){flag=0;break;}
		}
    }
	 if(flag==1)printf("巡游成功^o^\n");
	 else printf("无法全部巡游到啊T_T\n");
	 printf("如需再巡游,请输入1回车,如要结束,请输入0,请输入:");
	 scanf("%d",&lable);
	 if(lable==0)break;
    printf("请再输入行列值:");//重新新一轮巡游
    scanf("%d %d",&i,&j);
    l=(i-1)*n+j;
    }
}