搜索1015

题目大意:

给出起点和终点坐标，求出最短步数，每次走一个“日”字

解题思路:

bfs

代码:

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int vis[20][20];
string s1,s2;
struct ans
{
    int x;
    int y;
    int ste;
}n1,n2;
int dix[10]={-2,-2,-1,-1,1,1,2,2};
int diy[10]={-1,1,-2,2,-2,2,-1,1};
int ww(int a,int b)
{
    if(a>0&&a<=8&&b>0&&b<=8) return 1;
    return 0;
}
int BFS( )
{
    n1.ste=0;
    queue<ans> Q;
    Q.push(n1);
    while(!Q.empty())
    {
        n1=Q.front();
        Q.pop();
        if(n1.x==s2[1]-'0'&&n1.y==s2[0]-'a'+1) return n1.ste;
        for(int i=0;i<8;i++)
        {
            n2.x=n1.x+dix[i];
            n2.y=n1.y+diy[i];
            if(ww(n2.x,n2.y)&&!vis[n2.x][n2.y])
            {
                vis[n2.x][n2.y]=1;
                n2.ste=n1.ste+1;
                Q.push(n2);
            }
        }
    }
    return -1;
}

int main()
{
    //freopen("a.txt","r",stdin);
    while(cin>>s1>>s2)
    {
        int i,j;
        n1.x=s1[1]-'0';
        n1.y=s1[0]-'a'+1;
        for(i=0;i<20;i++)
            for(j=0;j<20;j++)
             vis[i][j]=0;
        vis[n1.x][n1.y]=1;
        int t=BFS();
            cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<t<<" knight moves."<<endl;
    }
    return 0;
}