2243是骑士问题，八个格子的，BFS，因为要最短路经，所以没有用A*,A*跑不出来，太慢了，因为要搜索到所有解啊！一直更新最优，而BFS，一层一层搜索，第一次得到的便是最短的了！300格子，标记的话，BFS遍历所有时间复杂度也算可以！500MS过！稍微剪枝即可！时间注意!要标记每层已经走过的情况时候要在入队的时候标记！大大降低复杂度！因为出队的时候，有些已经在队里了，但是还没有被标记，现在又让他入队！

1915，也是简单BFS过的，暴搜即可。标记一下。但是先用启发搜索怎么也过不了，TLE，用跑2W次就结束，但是WA，悲剧，用欧几里得距离作启发函数啊，奇怪，在几步之内到达目标附近，可能不是最优解了，因为这样不能像一层一层那样标记了，只能更新最小的情况！很多剪枝的时候要注意语句顺序！还有更新与剪枝的顺序！

#include
    
        //bfs#include
     
      #include
      
       #include
       
        using namespace std;int  absnum(int x,int y){    if(x>y) return x-y;    else return y-x;}bool mark[8][8];int a[8][8];int f[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};int minpath=15;struct xy{    int x,y;    int count;};void bfs(string from,string end){    queue
        
         q;    xy start;    start.x=from[0]-'a';    start.y=from[1]-'1';    start.count=0;    q.push(start);    int endx=end[0]-'a';    int endy=end[1]-'1';    if((start.x==endx&&absnum(start.y,endy)==1)||(start.y==endy&&absnum(start.x,endx)==1))    {        minpath=3;return;    }    while(!q.empty())    {        xy getfront=q.front();q.pop();        mark[getfront.x][getfront.y]=1;        if(getfront.count>6)return;      //无启发可以这样，一层一层，最多走7次。        if(getfront.x==endx&&getfront.y==endy)        {            if(minpath>getfront.count)minpath=getfront.count;        }        for(int i=0;i<8;i++)        {            xy next(getfront);            next.x+=f[i][0];            next.y+=f[i][1];            if(next.x>=0&&next.x<8&&next.y>=0&&next.y<8&&mark[next.x][next.y]==0)            {                if(next.count>minpath)continue;  //已经多了就不用了                next.count++;                q.push(next);              mark[next.x][next.y]=1;         //在这里标记！            }        }    }}int main(){    string from,end;    while(cin>>from>>end)    {        minpath=15;        memset(mark,0,sizeof(mark));        bfs(from,end);        cout<<"To get from "<
         
          <<" to "<
          
           <<" takes "<
           
            <<" knight moves."<
           
          
         
        
       
      
     
    

#include
    
          //bfs1915爆搜过#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int  absnum(int x,int y){    if(x>y) return (x-y);    else return (y-x);}int mark[301][301];int f[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};int minpath=300;struct xy{    int x,y;    int count;    double juli;    bool operator <(const xy &a)const    {        return a.juli
         
          q; xy start; start.x=from.x; start.y=from.y; start.count=0; start.juli=hamit(start,end); q.push(start); mark[start.x][start.y]=-1; int counted=0; while(!q.empty()) { xy getfront=q.top(); counted++; q.pop(); if(counted>10000) { if(hamit(getfront,end)>6)continue; } if(getfront.x==end.x&&getfront.y==end.y) { if(minpath>getfront.count) { minpath=getfront.count; } continue; } for(int i=0;i<8;i++) { xy next(getfront); next.x+=f[i][0]; next.y+=f[i][1]; if(next.x>=0&&next.x
          
           =0&&next.y
           
            
             =minpath)continue; //比最优差，剪枝！ if(next.count>daxiao/2+3)continue; if(mark[next.x][next.y]>next.count) { mark[next.x][next.y]=next.count; } if(next.x==end.x&&next.y==end.y) { if(minpath>next.count) { minpath=next.count; } continue; } q.push(next); } } } return;}int main(){ int na;cin>>na; while(na--) { cin>>daxiao; cin>>from.x>>from.y>>end.x>>end.y; minpath=daxiao; memset(mark,0x3f3f3f3f,sizeof(mark)); bfs(from,end); cout<
             
              <
             
            
           
          
         
        
       
      
     
    

#include
    
          //bfs，A*/WA不解ing#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int  absnum(int x,int y){    if(x>y) return (x-y);    else return (y-x);}int mark[301][301];int f[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};int minpath=300;struct xy{    int x,y;    int count;    double juli;    bool operator <(const xy &a)const    {        return a.juli
         
          q;    xy start;    start.x=from.x;    start.y=from.y;    start.count=0;    start.juli=hamit(start,end);    q.push(start);    mark[start.x][start.y]=-1;   // int counted=0;    while(!q.empty())    {        xy getfront=q.top();       // counted++;        //cout<
          
           <<"kkk"<
           
            20000)  //到达2W次，差不多可以出来！        {            return;        }*/      //  cout<
            
             <<":"<
             
              <<"-"<
              
               <
               
                getfront.count) mark[getfront.x][getfront.y]=getfront.count;        for(int i=0;i<8;i++)        {            xy next(getfront);            next.x+=f[i][0];            next.y+=f[i][1];            if(next.x>=0&&next.x
                
                 =0&&next.y
                 
                  =mark[next.x][next.y])continue; //注意这几个语句之间顺序！continue很重要！                   mark[next.x][next.y]=next.count;                 if(next.x==end.x&&next.y==end.y)                     {                           if(minpath>next.count)                            {                             minpath=next.count;                            }                        continue;                    }                  if(next.count>=minpath)continue;     //比最优差，剪枝！                 // if(next.count>daxiao/2+3)continue;                q.push(next);            }        }    }    return;}int main(){    int na;cin>>na;    while(na--)    {        cin>>daxiao;        cin>>from.x>>from.y>>end.x>>end.y;        minpath=daxiao;        memset(mark,0x3f3f3f3f,sizeof(mark));        bfs(from,end);        cout<
                  
                   <