骑士问题 C组模拟赛-白红宇

骑士问题 C组模拟赛

阅读量：6256 次

发布时间：2019-06-22

本文共 1353 字，大约阅读时间需要 4 分钟。

题目：

这道题形容起来很麻烦，可能看不懂我的代码，就放上来了

题目大意：

8*8的棋盘，有一些障碍物，骑士只可以像象棋中的”马”一样走”日”字，问在x点最少走几步到达y点

解题思路：

深搜/广搜

广搜比较快

不过深搜打起来比较简单

所以我用了深搜

源程序：

#include
    
     #include
     
      #include
      
       #define min(a,b) a>b?b:ausing namespace std;int b,a[9][9];int dx[9]={
   0,1,-1,2,-2,1,-1,2,-2};int dy[9]={
   0,2,-2,1,-1,-2,2,-1,1};int ans;void count(int x){ans=min(x,ans); return;}void dfs(int x1,int y1,int x2,int y2,int p)//x1,y1是当前坐标,x2,y2是目标坐标,p是当前的步数{    if (x1==x2&&y1==y2) {count(p); return;}//到目的地了    if (x1<1||y1<1||x1>8||y1>8||a[x1][y1]
       
        0||a[x1][y1]==-1) return;    //出棋盘或这是障碍或之前来过了，并且用的步数更少，说明就没用了    for (int i=1;i<=8;i++)    {        int x=x1+dx[i],y=y1+dy[i];        a[x1][y1]=p;//记录        dfs(x,y,x2,y2,p+1);//往下走    }}int main(){    int lon=0;    while (scanf("%d",&b),b!=-1)    {        memset(a,0,sizeof(a));//初始化        ans=2147483647;        char c,ch;        for (int i=1;i<=b;i++)        {            cin>>c>>ch;            int xx=(int)(c-96),yy=(int)(ch-48);            a[xx][yy]=-1;        }        cin>>c>>ch;        int x1=c-96,y1=ch-48;        cin>>c>>ch;        int x2=c-96,y2=ch-48;//上面一大串读入啊，初始化啊什么的        dfs(x1,y1,x2,y2,0);//开始搜        if (ans==2147483647) printf("Board %d: not reachable\n",++lon);        else printf("Board %d: %d moves\n",++lon,ans);//输出    }}