1372 - knight moves.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 102 行

#include <cstdio> 
#include <queue> 
#include <string> 
using namespace std; 
bool map[8][8]; 
struct infor 
{ 
    int x,y,time; 
     
    bool operator == (const infor t) 
    { 
        if(x==t.x && y==t.y) 
            return true; 
        else 
            return false; 
    } 
    void maketag() 
    { 
        map[x][y]=true; 
    } 
    bool isokay() 
    { 
        if(x<0 || y<0 || x>=8 || y>=8 || map[x][y]) 
            return false; 
        return true; 
    } 
}point[2]; 
int n; 
char s[5],d[5]; 
queue<infor> SQ; 

void bfs() 
{ 
    infor tmp,now; 
     
    while(!SQ.empty()) 
    { 
        now=SQ.front(); 
        SQ.pop(); 
        if(now==point[1]) 
        { 
            n=now.time; 
            return ; 
        } 
        else 
        { 
            now.maketag(); 
             
            tmp=now;tmp.x--;tmp.y-=2;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
                 
            tmp=now;tmp.x--;tmp.y+=2;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
             
            tmp=now;tmp.x++;tmp.y-=2;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
                 
            tmp=now;tmp.x++;tmp.y+=2;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
                 
            tmp=now;tmp.x-=2;tmp.y--;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
                 
            tmp=now;tmp.x-=2;tmp.y++;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
                 
            tmp=now;tmp.x+=2;tmp.y++;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
                 
            tmp=now;tmp.x+=2;tmp.y--;tmp.time++; 
            if(tmp.isokay()) 
                SQ.push(tmp); 
        } 
    } 
} 

int main() 
{ 
    while(scanf("%s %s",s,d)==2) 
    { 
        point[0].x=s[0]-'a';point[0].y=s[1]-'0'-1;point[0].time=0; 
        point[1].x=d[0]-'a';point[1].y=d[1]-'0'-1;point[1].time=0; 
         
        while(!SQ.empty()) 
            SQ.pop(); 
        memset(map,0,sizeof(map)); 
        SQ.push(point[0]); 
        bfs(); 
         
        printf("To get from %s to %s takes %d knight moves.\n",s,d,n); 
    } 
    return 0; 
}