wplounge wordpress主题/优化seo哪家好

马的移动
描述

小明很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：
给定两个棋盘上的方格a和b，马从a跳到b最少需要多少步？
现请你编程解决这个问题。

提示：国际象棋棋盘为8格*8格，马的走子规则为，每步棋先横走或直走一格，然后再往外斜走一格。

输入
输入包含多组测试数据。每组输入由两个方格组成，每个方格包含一个小写字母（a_{h），表示棋盘的列号，和一个整数（1}8），表示棋盘的行号。

输出
对于每组输入，输出一行“To get from xx to yy takes n knight moves.”。

输入样例 1

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

输出样例 1

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

思路：这是一道BFS的模板题，一般这种涉及到步数的用BFS会比DFS去写会更好。然后就是这个题目的条件中可以看出这个有8个方向，按照题目意思去写就可以了。

#include <bits/stdc++.h>
using namespace std;struct node {int x,y;int step;   //记录步数
};
int vis[10][10],cnt,sx,sy,ex,ey;
int dx[8] = { 1,-1, 1,-1, 2,-2, 2,-2};
int dy[8] = { 2, 2,-2,-2, 1, 1,-1,-1};  //一个八个方向
string s,e;
void bfs(){queue<node>q;    //定义一个队列node now,next;now.x = sx; now.y = sy;now.step = 0;vis[now.x][now.y] = 1;  //标记起点已经走过。q.push(now);     //while(!q.empty()){now = q.front();    //节点now是队列的第一个元素q.pop();        //将队列的头弹出if(now.x == ex&&now.y == ey){ //走到了终点cnt = now.step;}for(int i=0;i<8;i++){next.x = now.x + dx[i];next.y = now.y + dy[i];if(next.x>=0&&next.x<8&&next.y>=0&&next.y<8&&vis[next.x][next.y]==0){next.step = now.step+1;vis[next.x][next.y] = 1;  //标记该点已经走过了q.push(next);              //将该点压入队列}}}
}int main(){while(cin>>s>>e){memset(vis,0,sizeof(vis));sx = s[0]-'a';   //起点的横坐标sy = s[1]-'1';   //起点的纵坐标ex = e[0]-'a';ey = e[1]-'1';bfs();//cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<endl;cout<<"To get from "<<s<<" to "<<e<<" takes "<<cnt<<" knight moves."<<endl;}return 0;
}