1330：【例8.3】最少步数

1330：【例8.3】最少步数

【题目描述】

在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。 【输入】 A、B两点的坐标。 【输出】 最少步数。 【输入样例】

12 16 18 10

【输出样例】

8 9

解题思路：

这题想到的就是bfs，大致就是用队列将每一种结果保存，然后依次出队列，找到目标状态。一共有12个不同的方向可以选择，用一个二维数组保存方向向量，用另一个二维数组来记录棋盘上的点是否被走过。 代码：

#include<iostream> #include<queue> using namespace std; const int M = 105; bool mp[M][M] = { false };//整个棋盘的信息 int vis[12][2] = { {2,1},{2,2},{1,2},{-1,2},{-2,2},{-2,1},{-2,-1},{-2,-2},{-1,-2},{1,-2},{2,-2},{2,-1} };//vis为方向向量，一个有12个方向 struct crood { int x, y;//坐标 int step;//走到该点所需要得步数 };//crood记录每个点的位置以及多少步走到该点 int ans; void bfs(int x,int y) { queue<crood>que;//队列保存状态 crood now, next;//now是当前的状态，next表示下一步的状态 now.step = 0; now.x = x; now.y = y; mp[x][y] = true; que.push(now);//当前状态入队 while (!que.empty()) { now = que.front();//更新状态 que.pop();//出队 for (int i = 0; i < 12; i++) { next.x = now.x + vis[i][0]; next.y = now.y + vis[i][1]; next.step = now.step + 1;//走一步 if (next.x == 1 && next.y == 1)//达到目标 { ans = next.step; return; } if ((!mp[next.x][next.y]) && next.x > 0 && next.x < 101 && next.y>0 && next.y < 101) //该点没被走过，一定要注意是否越界 { mp[next.x][next.y] = true;//标记已走 que.push(next);//入队 } } } } int main() { int x, y; while (cin >> x >> y) { memset(mp, false, sizeof(mp)); bfs(x, y); cout << ans << endl; } return 0; }

bfs与dfs总结与详解