本文共 2806 字，大约阅读时间需要 9 分钟。
广度搜索，从起始点开始，每次向8个方向探索。直到到达终点。
这里面类似于树按层次遍历输出每一层的节点。cur记录本层的节点数目，next记录下层节点的数目。当cur==0即为本层处理完了，cur = next。处理下层。
另外，用一个checked数组记录该节点是否访问，避免重复计算。一个节点(x, y)到数组的index的映射使用一个简单的hash函数：index = x*len+y。
重复代码挺多的，不过AC后懒得改了。。。364k memory, 188ms.
有个，看着很高级的样子，但没去实现，不知道效率能高多少。
#include #include using namespace std;const int maxsize = 301 * 301;bool checked[maxsize];//int xstep[8] = {-1, -2, -2, -1, 1, 2, 2, 1};//int ystep[8] = {-2, -1, 1, 2, -2, -1, 1, 2};int knightmove(int sx, int sy, int ex, int ey, int len){ int move = 0; queue > que; que.push(make_pair (sx, sy)); int cur = 1, next = 0; while(!que.empty()) { pair now = que.front(); que.pop(); cur--; //move = checked[now.first * len + now.second]; if(now.first == ex && now.second == ey) { return move; } if(!checked[(now.first - 1) * len + (now.second - 2)] && now.first - 1 >= 0 && now.second - 2 >= 0) { que.push(make_pair (now.first - 1, now.second - 2)); checked[(now.first - 1) * len + (now.second - 2)] = true; next++; } if(!checked[(now.first - 2) * len + (now.second - 1)] && now.first - 2 >= 0 && now.second - 1 >= 0) { que.push(make_pair (now.first - 2, now.second - 1)); checked[(now.first - 2) * len + (now.second - 1)] = true; next++; } if(!checked[(now.first - 2) * len + (now.second + 1)] && now.first - 2 >= 0 && now.second + 1 < len) { que.push(make_pair (now.first - 2, now.second + 1)); checked[(now.first - 2) * len + (now.second + 1)] = true; next++; } if(!checked[(now.first - 1) * len + (now.second + 2)] && now.first - 1 >= 0 && now.second + 2 < len) { que.push(make_pair (now.first - 1, now.second + 2)); checked[(now.first - 1) * len + (now.second + 2)] = true; next++; } if(!checked[(now.first + 1) * len + (now.second - 2)] && now.first + 1 < len && now.second - 2 >= 0) { que.push(make_pair (now.first + 1, now.second - 2)); checked[(now.first + 1) * len + (now.second - 2)] = true; next++; } if(!checked[(now.first + 2) * len + (now.second - 1)] && now.first + 2 < len && now.second - 1 >= 0) { que.push(make_pair (now.first + 2, now.second - 1)); checked[(now.first + 2) * len + (now.second - 1)] = true; next++; } if(!checked[(now.first + 2) * len + (now.second + 1)] && now.first + 2 < len && now.second + 1 < len) { que.push(make_pair (now.first + 2, now.second + 1)); checked[(now.first + 2) * len + (now.second + 1)] = true; next++; } if(!checked[(now.first + 1) * len + (now.second + 2)] && now.first + 1 < len && now.second + 2 < len) { que.push(make_pair (now.first + 1, now.second + 2)); checked[(now.first + 1) * len + (now.second + 2)] = true; next++; } if(cur == 0) { move++; cur = next; next = 0; } }}int main(){ int n; cin>>n; for(int i = 0; i < n; ++i) { memset(checked, false, maxsize); int len; cin>>len; int sx, sy, ex, ey; cin>>sx>>sy>>ex>>ey; cout<
转载地址：http://nxxli.baihongyu.com/