BFS-Knight
看到群里童鞋说这个scanf会挂，于是我试了下，poj已提交网页就挂了，不知道为啥。
朴素的bfs，之前dfs练得多一些，图的dfs相比树的因为更复杂，需要visit来避免重复访问。poj2243, 这道就是基本的bfs了，好像也没有剪枝的策略。
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
//#include <unordered_set>
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
using namespace std;
struct node
{
int row;
int col;
int path;
};
int main()
{
//read;
//write;
char s[3],e[3];
while(~scanf("%s%s",s,e))
{
//cin>>e;
node start,end;
start.col=s[0]-'a';
start.row=s[1]-'1';
start.path=0;
end.col=e[0]-'a';
end.row=e[1]-'1';
queue<node> q;
q.push(start);
node p;
while(!q.empty())
{
p=q.front();
q.pop();
if(p.row==end.row && p.col== end.col)
{
break;
}
if(p.row-2 >=0 && p.col+1<=7)
{
node nd;
nd.row=p.row-2;nd.col=p.col+1;
nd.path=p.path+1;
q.push(nd);
}
if(p.row-1 >=0 && p.col+2<=7)
{
node nd;
nd.row=p.row-1;nd.col=p.col+2;
nd.path=p.path+1;
q.push(nd);
}
if(p.row+1 <=7 && p.col+2<=7)
{
node nd;
nd.row=p.row+1;nd.col=p.col+2;
nd.path=p.path+1;
q.push(nd);
}
if(p.row+2 <=7 && p.col+1<=7)
{
node nd;
nd.row=p.row+2;nd.col=p.col+1;
nd.path=p.path+1;
q.push(nd);
}
if(p.row+2 <=7 && p.col-1>=0)
{
node nd;
nd.row=p.row+2;nd.col=p.col-1;
nd.path=p.path+1;
q.push(nd);
}
if(p.row+1 <=7 && p.col-2>=0)
{
node nd;
nd.row=p.row+1;nd.col=p.col-2;nd.path=p.path+1;
q.push(nd);
}
if(p.row-1 >=0 && p.col-2>=0)
{
node nd;
nd.row=p.row-1;nd.col=p.col-2;nd.path=p.path+1;
q.push(nd);
}
if(p.row-2 >=0 && p.col-1>=0)
{
node nd;
nd.row=p.row-2;nd.col=p.col-1;nd.path=p.path+1;
q.push(nd);
}
}
cout<<"To get from "<<s<<" to "<<e<<" takes "<<p.path<<" knight moves."<<endl;
}
return 0;
}