首页 > 代码库 > 跳马问题
跳马问题
跳马
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:
在国际象棋中,马的走法与中车象棋类似,即俗话说的“马走日”,下图所示即国际象棋中马(K)在一步能到达的格子(其中黑色的格子是能到达的位置)。
现有一200*200大小的国际象棋棋盘,棋盘中仅有一个马,给定马的当前位置(S)和目标位置(T),求出马最少需要多少跳才能从当前位置到达目标位置。
输入:
本题包含多个测例。输入数据的第一行有一个整数N(1<=N<=1000),表示测例的个数,接下来的每一行有四个以空格分隔的整数,分别表示马当前位置及目标位置的横、纵坐标C(x,y)和G(x,y)。坐标由1开始。
输出:
对于每个测例,在单独的一行内输出一个整数,即马从当前位置跳到目标位置最少的跳数。
输入样例:
2
1 1 2 1
1 5 5 1
输出样例:
3
4
/* * @author Panos */ #include<iostream> #include<cstdio> #include<cstring> #include<fstream> #include<string> #include<algorithm> #include<vector> #include<ctime> #include<stack> #include<iomanip> #include<queue> //#include<cmath> #include<list> using namespace std; #define DBG 1 #define fori(i,a,b) for(int i = (a); i < (b); i++) #define forie(i,a,b) for(int i = (a); i <= (b); i++) #define ford(i,a,b) for(int i = (a); i > (b); i++) #define forde(i,a,b) for(int i = (a); i >= (b); i++) #define forls(i,n,a,b) for(int i = (a); i != (b); i = n[i]) #define mset(a,v) memset(a, v, sizeof(a)) #define mcpy(a,b) memcpy(a, b, sizeof(a)) #define dout DBG && cerr << __LINE__ << " >>| " #define checkv(x) dout << #x"=" << (x) << " | "<<endl #define checka(array,a,b) if(DBG) { \ dout<<#array"[] | " << endl; forie(i,a,b) cerr <<"["<<i<<"]="<<array[i]<<" |"<<((i-(a)+1)%5?" ":"\n"); if(((b)-(a)+1)%5) cerr<<endl; } #define redata(T, x) T x; cin >> x #define MIN_LD -2147483648 #define MAX_LD 2147483647 #define MIN_LLD -9223372036854775808 #define MAX_LLD 9223372036854775807 #define MAX_INF 18446744073709551615 inline int reint() { int d; scanf("%d",&d); return d; } inline long relong() { long l; scanf("%ld",&l); return l; } inline char rechar() { scanf(" "); return getchar(); } inline double redouble() { double d; scanf("%lf", &d); return d; } inline string restring() { string s; cin>>s; return s; } int a[205][205]; ///棋盘 const int dx[8]={-1,-2,-2,-1,1,2,2,1}; ///方向增量 const int dy[8]={2,1,-1,-2,-2,-1,1,2}; struct node { int x, y; }; void BFS(int start_x, int start_y, int end_x, int end_y) { queue<node> Q; node N; N.x = start_x; N.y = start_y; Q.push(N); a[start_x][start_y] = 0; while(!Q.empty()) { N = Q.front(); Q.pop(); int x = N.x, y = N.y; if(x == end_x && y == end_y) break; fori(i,0,8) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 1 && nx <= 200 && ny >= 1 && ny <= 200 && a[nx][ny]<0) { a[nx][ny] = a[x][y] + 1; N.x = nx; N.y = ny; Q.push(N); } } } } int main() { int start_x, start_y, end_x, end_y; while(scanf("%d%d%d%d",&start_x,&start_y,&end_x,&end_y)==4) { mset(a,-1); BFS(start_x,start_y,end_x,end_y); cout << a[end_x][end_y]<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。