#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.
",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.
",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. ",a+96,b,c+96,d,BFS(src ,res)); } return 0; }
#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. ",row,col,end,ed,min); } return 0; }
#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.
",row,col,end,ed,min);
}
return 0;
}