本文主要是介绍sdnu 1027.马踏飞燕(续)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接： http://210.44.14.31/problem/show/1027
考查BFS。
思路：以起点为根，逐渐向外扩展。
关键点：怎样维护你走的第几步。
有两种方法：
1.棋盘int，结点pair：可以用棋盘来维护，
上一步棋盘位置的步数+1=下一步棋盘位置的步数。
2.棋盘bool，结点struct ：可以用结点来维护，就像一棵树，起始点是根，
每次BFS便往外扩展一圈，所以child的步数=parent的步数+1。
（struct里面设第三个变量记录步数）
代码如下（第一种方法）：
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<cstdio>
using namespace std;
int qp[2001][2001];
int main()
{int nextx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };int nexty[8] = {-2,-1, 1, 2, 2, 1, -1, -2 };int x, y, m, n;memset(qp, 0, sizeof(qp));pair<int, int>pa;queue<pair<int, int> >q;scanf_s("%d%d%d%d", &x, &y, &m, &n);pa.first = x; pa.second = y;q.push(pa);while (!q.empty()) {pair<int, int>temp = q.front();q.pop();if (qp[temp.first][temp.second] <= 199) //200步就不用走了{for (int i = 0; i < 8; i++){pa.first = temp.first + nextx[i]; pa.second = temp.second + nexty[i];if (pa.first >= 0 && pa.first < 2000 && pa.second >= 0 && pa.second < 2000){if (pa.first == m&&pa.second == n) //找到直接跳出循环goto end;if (qp[pa.first][pa.second] == 0) //若该点没走过则赋值{qp[pa.first][pa.second] = qp[temp.first][temp.second] + 1;q.push(pa);}}}} }cout << "N" << endl;return 0;
end: cout << "Y" << endl;return 0;
}这篇关于sdnu 1027.马踏飞燕(续)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
