HOJ 1440 Knight Moves -------简单搜索 BFS 求l两点之间最小的到达步数
HOJ 1440 Knight Moves
//题意：给定两个点的坐标，按照国际象棋中骑士的走法（有点类似于中国象棋的马踏斜日，可以向八个方向走），问最短的步子//思路:典型搜索的题目，一般求最小的步子用BFS//调试注意：.....#include<iostream>#include<queue>#include<cstring>#define maxlen 9using namespace std;int mat[maxlen][maxlen];struct node{ int x; int y; int step;}s,e;int dir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};int BFS(node s,node e){ memset(mat,0,sizeof(mat));//每个点都可以走 queue<node> q; node ol,ne; while(!q.empty()) { q.pop(); } s.step=0; q.push(s); while(!q.empty()) { ol=q.front(); q.pop(); if(ol.x==e.x&&ol.y==e.y){return ol.step;} else { for(int i=0;i<8;i++) { ne.x=ol.x+dir[i][0]; ne.y=ol.y+dir[i][1]; ne.step=ol.step; if(mat[ne.x][ne.y]||ne.x<1||ne.x>8||ne.y<1||ne.y>8) continue ; else { mat[ne.x][ne.y]=1; ne.step++; q.push(ne); } } } } return ne.step;}int main(){ char m,n; while(cin >> m >>s.y >> n >> e.y) { s.x=m-'a'+1; e.x=n-'a'+1; cout << "To get from " << m << s.y << " to " << n << e.y << " takes "<< BFS(s,e) << " knight moves."<<endl; } return 0;}