439 - Knight Moves （UVA）

题目链接如下：

Online Judge

UVA439 骑士的移动 - 锦依卫议事堂 - 洛谷博客 这里有好几个特别厉害的解法...先存着慢慢看。

我的代码如下：

#include <iostream>
#include <deque>
#include <string>
// #define debugstruct node{std::string loc;int step;
};
std::string s1, s2;
int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};int calStep(){if (s1 == s2){return 0;}node temp;temp.loc = s1;temp.step = 0;std::deque<node> dq;dq.push_back(temp);while (!dq.empty()){node curr = dq.front();dq.pop_front();for (int u = 0; u < 8; ++u){node tmp;tmp.loc.push_back(curr.loc[0] + dx[u]);tmp.loc.push_back(curr.loc[1] + dy[u]);if (tmp.loc == s2){return curr.step + 1;}if (tmp.loc[0] >= 'a' && tmp.loc[0] <= 'h' && tmp.loc[1] >= '1' && tmp.loc[1] <= '8'){tmp.step = curr.step + 1;dq.push_back(tmp);}}}
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (std::cin >> s1 >> s2){printf("To get from %s to %s takes %d knight moves.\n", s1.c_str(), s2.c_str(), calStep());}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}