原题入口： http://acm.hdu.edu.cn/showproblem.php?pid=1372
昨天(2017/11/29)中午写了第一篇笔记也是第一篇BFS笔记，下午考试就用上了，美滋滋的AC~; 今天晚上又碰到了BFS，套版子题~; 除了骑士的移动方式稍微有点费解…… 大概是这样：(M代表起点，E代表一步可以到达的位置) O E O E O E O O O E O O M O O E O O O E O E O E O 所以代码很好写~
/* Judge Status: Accepted Pro.ID : 1372 Exe.Time : 15MS Exe.Memory : 1676K Code Len. : 1694B Language : G++ Author : BelieberJ */ #include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <queue> using namespace std; struct Node { int x,y,step; }; queue<Node>q; int sx,sy,tx,ty,direct; int vis[8][8]; int dx[8] = {-2,-2,-1,-1,1,1,2,2}; int dy[8] = {1,-1,2,-2,2,-2,1,-1}; int bfs(int sx,int sy) { while (!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); Node st; st.x = sx; st.y = sy; st.step = 0; q.push(st); vis[st.x][st.y] = 1; while (!q.empty()) { Node cur = q.front(); q.pop(); for (direct = 0; direct < 8; direct++) { Node nx; nx.x = cur.x + dx[direct]; nx.y = cur.y + dy[direct]; nx.step = cur.step + 1; if (nx.x == tx && nx.y == ty) return nx.step; if (nx.x < 0 || nx.y < 0 || nx.x >= 8 || nx.y >= 8 || vis[nx.x][nx.y]) continue; vis[nx.x][nx.y] = 1; q.push(nx); } } } int main() { int ans; char c[10]; while ((c[0] = getchar()) != EOF) { sx = c[0] - 'a'; //!可能从a开始 c[1] = getchar(); //!读取数字，可能从1开始 sy = c[1] - '1'; c[2] = getchar(); //!处理空格 c[2] = getchar(); tx = c[2] - 'a'; c[3] = getchar(); ty = c[3] - '1'; c[4] = getchar(); if (sx == tx && sy == ty) printf("To get from %c%c to %c%c takes 0 knight moves.\n",c[0],c[1],c[2],c[3]); else { ans = bfs(sx,sy); printf("To get from %c%c to %c%c takes %d knight moves.\n",c[0],c[1],c[2],c[3],ans); } } return 0; }printf(“就是这么轻松丫~\n”);
