UVa 439,Knight Moves

BFS模板大水题

虽然是大水题，但是1A过的还是蛮开心的~

感觉需要注意的地方就是下标要ch-'b'（有些人比如我总是习惯性的减a，这题下标是从1开始的，当然你就是从0开始当我没说= =）...减a的会在样例h8过不去的

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 100
using namespace std;
int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={-2,-1,1,2,2,1,-1,-2};
int ans;
int p,qq,x,y;
struct Node{
    int x,y;
    int cnt;
};
int bfs(){
    queue<Node> q;
    Node u;
    u.x=x;u.y=y;u.cnt=0;
    q.push(u);
    while (!q.empty()){
        u=q.front();q.pop();
        Node v;
        if ((u.x==p)&&(u.y==qq)) {
            ans=u.cnt;
            return 0;
        }
        for (int i=0;i<8;i++){
            v.x=u.x+dx[i];
            v.y=u.y+dy[i];
            v.cnt=u.cnt+1;
            if (v.x>=1&&v.x<=8&&v.y>=1&&v.y<=8){
                q.push(v);
            }
        }
    }
}
int main()
{
    char ch1,ch2;
    while (cin>>ch1>>x){
        y=ch1-'a'+1;
        cin>>ch2>>p;
        qq=ch2-'a'+1;
        bfs();
        cout<<"To get from "<<ch1<<x<<" to "<<ch2<<p<<" takes "<<ans<<" knight moves."<<endl;
    }
}