## sicily 1936. Knight Moves

2019年11月11日 ⁄ 综合 ⁄ 共 1176字 ⁄ 字号 评论关闭

#include<iostream>
using namespace std;
int knight[8][8];
int x[]={1,1,2,2,-1,-1,-2,-2};
int y[]={2,-2,1,-1,2,-2,1,-1};
void dfs(int si,int sj,int moves)
{
if(si<0||sj<0||si>=8||sj>=8||moves>=knight[si][sj])return;
knight[si][sj]=moves;
for(int i=0;i<8;i++)
dfs(si+x[i],sj+y[i],moves+1);
}
int main()
{
int t;
cin >> t;
while(t--)
{
char a[10],b[10];
cin>>a>>b;
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
knight[i][j]=10;
dfs(a[0]-'a',a[1]-'1',0);
cout<<"To get from "<<a<<" to "<<b<<" takes "<<
knight[b[0]-'a'][b[1]-'1']<<" knight moves."<<endl;
}
return 0;
}

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

struct point{
int x,y;
int c;
}from,to;

int main(){
queue<point> q;
int t;
char src[3],dist[3];
int dx[]={1,1,2,2,-1,-1,-2,-2};
int dy[]={2,-2,1,-1,2,-2,1,-1};
cin >> t;
while(t--){
cin >> src >> dist;
printf("To get from %s to %s ",src,dist);
while(!q.empty()) q.pop();
from.x=src[0]-'a';
from.y=src[1]-'1';
from.c=0;
to.x=dist[0]-'a';
to.y=dist[1]-'1';
q.push(from);
point temp;
while(true)
{
from=q.front();
q.pop();
if(from.x==to.x&&from.y==to.y) break;
for(int i=0;i<8;i++){
temp.x=from.x+dx[i];
temp.y=from.y+dy[i];
temp.c=from.c+1;
if(temp.x<0||temp.x>7||temp.y<0||temp.y>7)continue;
q.push(temp);
}
}
printf("takes %d knight moves.\n",from.c);
}
}