069.骑士巡游

简介: 069.骑士巡游
//
/*                       骑士巡游问题                                   */
/
#include <stdio.h>
int f[11][11] ;                                /*定义一个矩阵来模拟棋盘*/
int adjm[121][121];/*标志矩阵,即对于上述棋盘,依次进行编号
        1--121(行优先)可以从一个棋盘格i跳到棋盘格j时,adjm[i][j]=1*/
void creatadjm(void);                            /*创建标志矩阵函数声明*/
void mark(int,int,int,int);                     /*将标志矩阵相应位置置1*/
void travel(int,int);                                    /*巡游函数声明*/
int n,m;                                 /*定义矩阵大小及标志矩阵的大小*/
/******************************主函数***********************************/
int main()
{
    int i,j,k,l;
    printf("Please input size of the chessboard: ");  /*输入矩阵的大小值*/
  scanf("%d",&n);
    m=n*n;
    creatadjm();                                         /*创建标志矩阵*/
  puts("The sign matrix is:");
    for(i=1;i<=m;i++)                                /*打印输出标志矩阵*/
    {
        for(j=1;j<=m;j++) 
      printf("%2d",adjm[i][j]);
        printf("\n");
    }
    printf("Please input the knight's position (i,j): "); /*输入骑士的初始位置*/
    scanf("%d %d",&i,&j);
    l=(i-1)*n+j;                   /*骑士当前位置对应的标志矩阵的横坐标*/
    while ((i>0)||(j>0))                             /*对骑士位置的判断*/
    {
        for(i=1;i<=n;i++)                              /*棋盘矩阵初始化*/
            for(j=1;j<=n;j++)
                f[i][j]=0;
        k=0;                                             /*所跳步数计数*/
        travel(l,k);                                /*从i,j出发开始巡游*/
        puts("The travel steps are:");
        for(i=1;i<=n;i++)                      /*巡游完成后输出巡游过程*/
    {
            for(j=1;j<=n;j++) 
          printf("%4d",f[i][j]);
            printf("\n");
    }
        printf("Please input the knight's position (i,j): ");/*为再次巡游输入起始位置*/
      scanf("%d %d",&i,&j);
        l=(i-1)*n+j;
    }
  puts("\n Press any key to quit... ");
  getch();
    return 0;
}
/*****************************创建标志矩阵子函数*************************/
void creatadjm()
{
    int i,j;
    for(i=1;i<=n;i++)                                   /*巡游矩阵初始化*/
        for(j=1;j<=n;j++)
            f[i][j]=0;
    for(i=1;i<=m;i++)                                   /*标志矩阵初始化*/
        for(j=1;j<=m;j++)
            adjm[i][j]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(f[i][j]==0)           /*对所有符合条件的标志矩阵种元素置1*/
      {
                f[i][j]=1;
                if((i+2<=n)&&(j+1<=n)) mark(i,j,i+2,j+1);
                if((i+2<=n)&&(j-1>=1)) mark(i,j,i+2,j-1);
                if((i-2>=1)&&(j+1<=n)) mark(i,j,i-2,j+1);
                if((i-2>=1)&&(j-1>=1)) mark(i,j,i-2,j-1);
                if((j+2<=n)&&(i+1<=n)) mark(i,j,i+1,j+2);
                if((j+2<=n)&&(i-1>=1)) mark(i,j,i-1,j+2);
                if((j-2>=1)&&(i+1<=n)) mark(i,j,i+1,j-2);
                if((j-2>=1)&&(i-1>=1)) mark(i,j,i-1,j-2);
      } 
    return;
}
/*********************************巡游子函数*******************************/
void travel(int p,int r)
{
    int i,j,q;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(f[i][j]>r) f[i][j]=0;              /*棋盘矩阵的置〉r时,置0*/
    r=r+1;                                                   /*跳步计数加1*/
    i=((p-1)/n)+1;                                  /*还原棋盘矩阵的横坐标*/
    j=((p-1)%n)+1;                                  /*还原棋盘矩阵的纵坐标*/
    f[i][j]=r;                              /*将f[i][j]做为第r跳步的目的地*/
    for(q=1;q<=m;q++)           /*从所有可能的情况出发,开始进行试探式巡游*/
  {
        i=((q-1)/n)+1;
        j=((q-1)%n)+1;
        if((adjm[p][q]==1)&&(f[i][j]==0)) 
      travel(q,r);                                    /*递归调用自身*/
    }
    return;
}
/*************************赋值子函数***************************************/
void mark(int i1,int j1,int i2,int j2)
{
    adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
    adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
    return;
}
相关文章
|
1月前
|
弹性计算 安全 Linux
幻兽帕鲁未响应?自建palworld服务器不卡还稳定
如何自建幻兽帕鲁服务器?基于阿里云服务器搭建幻兽帕鲁palworld服务器教程来了,一看就懂系列。本文是利用OOS中幻兽帕鲁扩展程序来一键部署幻兽帕鲁服务器,阿里云百科分享官方基于阿里云服务器快速创建幻兽帕鲁服务器教程
138 0
|
1月前
|
云安全 监控 安全
云服务器遇到DDOS的防护方案
DDoS攻击是云服务器面临的重要安全威胁之一。为了保障服务器的稳定性和安全性,我们需要采取多种措施进行防范
|
1月前
|
弹性计算 网络安全 文件存储
ECS热门应用 | 安装家用内网穿透服务
使用云服务器ECS,让家庭网络可以被外部网络访问。不在家时,也可以读取备份资料。
|
1月前
|
算法 Java 定位技术
分享104个益智休闲安卓游戏源码,总有一款适合你
分享104个益智休闲安卓游戏源码,总有一款适合你
278 1
|
10月前
|
文件存储 网络架构 Docker
无需公网IP,快速远程登录家里的威联通NAS
无需公网IP,快速远程登录家里的威联通NAS
|
Linux
阿里云学生机
使用学生机的体验
388 0
|
弹性计算 前端开发 网络安全
学生免费ECS使用体验+校园网内网穿透配置
学生免费ECS使用体验+校园网内网穿透配置
532 0
学生免费ECS使用体验+校园网内网穿透配置
|
弹性计算 NoSQL Java
阿里云ECS服务器使用体验
描述了我一段时间使用阿里云ECS服务器的感受
137 0
阿里云ECS服务器使用体验
|
弹性计算 Cloud Native Linux
|
弹性计算 编解码 数据可视化
阿里ECS服务器使用体验
在Java学习过程中接触到云服务器,通过搭建环境、安装软件和解决遇到的问题,对云服务器和Java开发有了更深入的理解。
阿里ECS服务器使用体验