#include <stdio.h>
#include <iostream>
#include <queue>

int move[8][2] ={{1,2},{2,1},{-1,-2},{-2,-1},{-1,2},{-2,1},{2,-1},{1,-2} };
bool used[10][10];
using namespace std;

struct point {
 int x;int y;
 int step;
};

int  BFS(point src ,point res) {

 queue<point> my;
 my.push(src);
 while( !my.empty() ) {
  point temp = my.front();
  point t ;
  if(temp.x == res.x && temp.y == res.y) return temp.step;
  for(int i = 0 ;i < 8; i++ ) {
   t.x = temp.x + move[i][0];
   t.y = temp.y + move[i][1];
   if(t.x>0&&t.x<9&&t.y>0&&t.y<9 && 0 == used[t.x][t.y]) {
    t.step = temp.step+1;
    used[t.x][t.y] = 1;
    my.push(t);
   }
  }
  my.pop();

 }
 return -1;
}
int main() {

 char a,c; int b,d;
 while(cin>>a>>b>>c>>d) {
  memset(used,0,sizeof(used));
  a-=96;  c-=96;
  point src,res;
  src.x = a; src.y = b;
  used[a][b] = 1;
  src.step = 0;
  res.x = c; res.y = d;
  printf("To get from %c%d to %c%d takes %d knight moves.\n",a+96,b,c+96,d,BFS(src ,res));
 }
 return 0;
}

#include <stdio.h>
#include <iostream>
#include <queue>

int move[8][2] ={{1,2},{2,1},{-1,-2},{-2,-1},{-1,2},{-2,1},{2,-1},{1,-2} };
bool used[10][10];
using namespace std;

struct point {
 int x;int y;
 int step;
};

int  BFS(point src ,point res) {

 queue<point> my;
 my.push(src);  //
 while( !my.empty() ) {
  point cur = my.front();
  point t ;
  if(cur.x == res.x && cur.y == res.y) return cur.step;
  for(int i = 0 ;i < 8; i++ ) {
   t.x = cur.x + move[i][0];
   t.y = cur.y + move[i][1];
   if(t.x>0&&t.x<9&&t.y>0&&t.y<9 && 0 == used[t.x][t.y]) {
    t.step = cur.step+1;
    used[t.x][t.y] = 1;
    my.push(t);
   }
  }
  my.pop();

 }
 return -1;
}
int main() {

 char a,c; int b,d;
 while(cin>>a>>b>>c>>d) {
  memset(used,0,sizeof(used));
  a-=96;  c-=96;
  point src,res;
  src.x = a; src.y = b;
  used[a][b] = 1;
  src.step = 0;
  res.x = c; res.y = d;
  printf("To get from %c%d to %c%d takes %d knight moves.\n",a+96,b,c+96,d,BFS(src ,res));
 }
 return 0;
}

#include <stdio.h>#include <iostream>#include <queue>int move[8][2] ={{1,2},{2,1},{-1,-2},{-2,-1},{-1,2},{-2,1},{2,-1},{1,-2} };bool used[10][10];using namespace std;struct point {    int x;int y;    int step;};int  BFS(point src ,point res) {    queue<point> my;    my.push(src);    while( !my.empty() ) {        point temp = my.front();        point t ;        if(temp.x == res.x && temp.y == res.y) return temp.step;        for(int i = 0 ;i < 8; i++ ) {            t.x = temp.x + move[i][0];            t.y = temp.y + move[i][1];            if(t.x>0&&t.x<9&&t.y>0&&t.y<9 && 0 == used[t.x][t.y]) {                t.step = temp.step+1;                used[t.x][t.y] = 1;                my.push(t);            }        }        my.pop();    }    return -1;}int main() {    char a,c; int b,d;    while(cin>>a>>b>>c>>d) {        memset(used,0,sizeof(used));        a-=96;  c-=96;        point src,res;        src.x = a; src.y = b;        used[a][b] = 1;        src.step = 0;        res.x = c; res.y = d;        printf("To get from %c%d to %c%d takes %d knight moves.\n",a+96,b,c+96,d,BFS(src ,res));    }    return 0;}

View Code

#include <iostream>#include <stdio.h>#include <string.h>#include <queue>using namespace std;int c[9][9];int dir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};typedef struct{    int x,y,count;}node;node start,finish;int bfs(){    memset(c,0,sizeof(c));    node pre,cur;    start.count = 0;    queue<node> q;    q.push(start);    c[start.x][start.y] = 1;        while(!q.empty())    {        pre = q.front();        q.pop();        if(pre.x == finish.x&&pre.y == finish.y)        return pre.count;        for(int i = 0; i < 8; i++)        {            cur.x = pre.x + dir[i][0];            cur.y = pre.y + dir[i][1];            if(cur.x<1||cur.x>8||cur.y<1||cur.y>8)continue;            if(c[cur.x][cur.y]==1)continue;            c[cur.x][cur.y] = 1;            cur.count = pre.count + 1;            q.push(cur);        }    }    return -1;}int main(){    char row,end;    int col,ed;    int min;    while(scanf("%c",&row)!=EOF)    {        scanf("%d",&col);        getchar();        scanf("%c%d",&end,&ed);        getchar();        start.x = row-‘a‘+1;        start.y = col;        finish.x = end-‘a‘+1;        finish.y = ed;        if(start.x==finish.x&&start.y==finish.y)        min = 0;        else  min = bfs();        printf("To get from %c%d to %c%d takes %d knight moves.\n",row,col,end,ed,min);    }    return 0;}

View Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int c[9][9];
int dir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
typedef struct
{
    int x,y,count;
}node;
node start,finish;
int bfs()
{
    memset(c,0,sizeof(c));
    node pre,cur;
    start.count = 0;
    queue<node> q;
    q.push(start);
    c[start.x][start.y] = 1;
   
    while(!q.empty())
    {
        pre = q.front();
        q.pop();
        if(pre.x == finish.x&&pre.y == finish.y)
        return pre.count;
        for(int i = 0; i < 8; i++)
        {
            cur.x = pre.x + dir[i][0];
            cur.y = pre.y + dir[i][1];
            if(cur.x<1||cur.x>8||cur.y<1||cur.y>8)continue;
            if(c[cur.x][cur.y]==1)continue;
            c[cur.x][cur.y] = 1;
            cur.count = pre.count + 1;
            q.push(cur);
        }
    }
    return -1;
}
int main()
{
    char row,end;
    int col,ed;
    int min;
    while(scanf("%c",&row)!=EOF)
    {
        scanf("%d",&col);
        getchar();
        scanf("%c%d",&end,&ed);
        getchar();
        start.x = row-‘a‘+1;
        start.y = col;
        finish.x = end-‘a‘+1;
        finish.y = ed;
        if(start.x==finish.x&&start.y==finish.y)
        min = 0;
        else  min = bfs();
        printf("To get from %c%d to %c%d takes %d knight moves.\n",row,col,end,ed,min);
    }
    return 0;
}