程序设计大赛---骑士巡游

本文主要是介绍程序设计大赛---骑士巡游，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个8*8的国际象棋棋盘，在这64个格子中指定一个起点和一个终点，求“马”从起点跳到终点所需的最少次数.

输入：

输入文件包含多组测试数据，每组数据占一行，包含起点和终点的两个坐标，坐标格式如下：首先是一个字母（a~h）表示所在的列，紧跟着是一个数字（1~8）表示所在的行，两个坐标第一个表示起点，第二个表示终点，中间用一个空格隔开。

输出：

对于输入文件中每一组数据块，输出一个整数表示从起点到终点要跳的最少次数，每个输出占一行。

输入样本：

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

输出样本：

2
4
2
6
5
6
1
0

我的程序：

#include<iostream.h>
#include<stdio.h>

int first_en=1;     //判断是否是第一次

//写文件
void mywrite(int count,int first)
{
    FILE *pt;
    pt=fopen("output.txt","a");
    if(first==1)
        fprintf(pt,"%d",count);
    else
        fprintf(pt,"/n%d",count);
    fclose(pt);
}
//清空文件
void clearfile()
{
    FILE *pt;
    pt=fopen("output.txt","w");
    fclose(pt);
}
//回溯算法

void knight(int a[][8],int dir[][2],int n1,int m1,int n2,int m2,int count,int min,int o1,int o2)
{
    if(min>count && a[o1][o2]!=0)
    {
        int i,j;
        int nn,mm;
        if(n1==n2 && m1==m2)   //是否结束
        {
            mywrite(count,first_en);
            first_en=0;        //将第一次标志变为0
            min=count;
            for(i=0;i<8;i++)
            {
                for(j=0;j<8;j++)
                    a[i][j]=0;
            }
        }
        else
        {
            for(i=0;i<8;i++)
            {
                if(min<count)
                    break;
                else
                {
                    nn=n1+dir[i][0];
                    mm=m1+dir[i][1];
                    if(nn>=0 && nn<=7 && mm>=0 && mm<=7 && a[nn][mm]==0 && a[o1][o2]!=0)
                    {
                        a[nn][mm]=1;
                        knight(a,dir,nn,mm,n2,m2,count+1,min,o1,o2);
                        a[nn][mm]=0;
                    }
                }
            }
        }
    }
}

void main()
{
    int a[8][8];
    clearfile();
    FILE *pt;
    char str1[2],str2[2];
    int i,j,min;
    int o1,o2;
    int o3,o4;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
            a[i][j]=0;
    }
    if(NULL==(pt=fopen("input.txt","r")))
    {
        cout<<"can't open input.txt!"<<endl;
    }
    else
    {
        while(fscanf(pt,"%s",str1)!=EOF)
        {
            fscanf(pt,"%s",str2);
            o1=str1[0]-'a';
            o2=str1[1]-'0'-1;
            o3=str2[0]-'a';
            o4=str2[1]-'0'-1;
            a[o1][o2]=1;
            int dir[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
            for(min=1;min<64;min++)
            {
                if(a[o1][o2]==0)
                    break;
                else
                    knight(a,dir,o1,o2,o3,o4,0,min,o1,o2);
            }
        }

        fclose(pt);
    }
}