小记:这题看懂题意就简单了
题意:国际象棋的马的走法,可以有八个方向走,和中国象棋马一样的走法。8*8地图上,给你一个起点一个终点,问你最少到达步数
思路:bfs
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define REP(a,b,c) for(int a = b; a < c; ++a) #define eps 10e-8 const int MAX_ = 10010; const int N = 100010; const int INF = 0x7fffffff; bool vis[MAX_][MAX_]; int dir[8][2] = {{1,-2}, {-1,-2},{-2,-1},{-2,1},{-1,2}, {1,2},{2,1},{2,-1}}; bool flag; int n, m; struct point { int x, y; int step; }end; int bfs(point start) { queue<point> q; start.step = 0; q.push(start); vis[start.x][start.y] = 1; while(!q.empty()){ point cur = q.front(); q.pop(); if(cur.x == end.x && cur.y == end.y){ //printf("%d\n", cur.step); return cur.step; } //printf("cur:[%d, %d]\n", cur.x, cur.y); REP(i, 0, 8){ point nt; nt.x = cur.x + dir[i][1]; nt.y = cur.y + dir[i][0]; nt.step = cur.step + 1; if((nt.x > 0 && nt.x <= 8) && (nt.y > 0 && nt.y <= 8)){ //printf("[%d, %d]\n", nt.x, nt.y); if(!vis[nt.x][nt.y]){ vis[nt.x][nt.y] = 1; q.push(nt); } } } } return -1; } int main() { int T; char s[10], t[10]; while(~scanf("%s%s", s, t)) { point start; start.x = s[1] - '0'; start.y = s[0] - 'a'+1; end.x = t[1] - '0'; end.y = t[0] - 'a'+1; //printf("coor:[%d, %d] [%d, %d]\n",start.x, start.y, end.x, end.y); mst(vis, 0 ); int ans = bfs(start); printf("To get from %s to %s takes %d knight moves.\n", s,t,ans); } return 0; }