// 题意：输入标准国际象棋棋盘上的两个格子，求马最少需要多少步从起点跳到终点
BFS求最短路：
bfs并维护距离状态cnt， vis记录是否访问过
#include#include #include #include #include #include using namespace std;int r1, c1, r2, c2;const int N=8;int vis[N][N];const int dr[] = {-2,-2,-1,-1, 1,1, 2,2};const int dc[] = {-1, 1,-2, 2,-2,2,-1,1};struct State { int r, c; int cnt; State(int r=0, int c=0, int cnt=0):r(r),c(c),cnt(cnt) {} bool operator == (const State& rhs) { return r==rhs.r && c==rhs.c; }};void tr(char* p, int &r, int &c){ r=p[0]-'a'; c=p[1]-'1';}int bfs(){ State f(r1, c1, 0), t(r2, c2); if(f==t) return 0; queue Q; Q.push(f); vis[r1][c1]=1; while(!Q.empty()) { State s=Q.front(); Q.pop(); if(s==t) return s.cnt; for(int i=0;i<8;i++) { int nr, nc; nr=s.r+dr[i]; nc=s.c+dc[i]; if(nr>=0 && nr<8 && nc>=0 && nc<8 && !vis[nr][nc]) { Q.push(State(nr, nc, s.cnt+1)); vis[nr][nc]=1; } } } return -1;}int main(){#ifndef ONLINE_JUDGE freopen("./uva439.in" , "r", stdin);#endif char p1[3]; char p2[3]; while(scanf("%s%s", p1, p2)!=EOF) { tr(p1, r1, c1); tr(p2, r2, c2); memset(vis, 0, sizeof vis); int cnt=bfs(); printf("To get from %s to %s takes %d knight moves.\n", p1, p2, cnt); } return 0;}
lrj代码：
vis记录是否访问过， d记录各个格子的距离（这个要学习）
// UVa439 Knight Moves// Rujia Liu// 题意：输入标准国际象棋棋盘上的两个格子，求马最少需要多少步从起点跳到终点#include#include #include using namespace std;struct State { int r, c; State(int r, int c):r(r),c(c) {}};const int dr[] = {-2,-2,-1,-1, 1,1, 2,2};const int dc[] = {-1, 1,-2, 2,-2,2,-1,1};int d[8][8], vis[8][8]; int bfs(int r1, int c1, int r2, int c2) { if(r1 == r2 && c1 == c2) return 0; queue Q; d[r1][c1] = 0; vis[r1][c1] = 1; Q.push(State(r1, c1)); while(!Q.empty()) { State s = Q.front(); Q.pop(); for(int i = 0; i < 8; i++) { int newr = s.r + dr[i]; int newc = s.c + dc[i]; if(newr >= 0 && newr < 8 && newc >= 0 && newc < 8 && !vis[newr][newc]) { Q.push(State(newr, newc)); vis[newr][newc] = 1; d[newr][newc] = d[s.r][s.c] + 1; if(newr == r2 && newc == c2) return d[newr][newc]; } } } return -1; } int main() { char s[9], t[9]; while(scanf("%s%s", s, t) == 2) { memset(vis, 0, sizeof(vis)); int ans = bfs(s[0]-'a', s[1]-'1', t[0]-'a', t[1]-'1'); printf("To get from %s to %s takes %d knight moves.\n", s, t, ans); } return 0;}