问题描述
一个8×8的棋盘上有一个马初始位置为(a,b),他想跳到(c,d),问是否可以?如果可以,最少要跳几步?
输入格式
一行四个数字a,b,c,d。
输出格式
如果跳不到,输出-1;否则输出最少跳到的步数。
样例输入
1 1 2 3
样例输出
1
嗯…蓝桥上的一个题,一开始用的dfs后来老师说bfs的复杂度啥的好一些,又改进了一下
dfs版本:
#includeusing namespace std; //求从(a,b)到(c,d)的最少步数,step为当前步数,min_step为已求得的最小步数 int a, b;//起点 int c, d;//终点 int min_step = -1;//已求得的最小步数 int board[9][9] = {0};//棋盘 //尝试第step步走到(c,d) void try_step(int i, int j, int step) { if(min_step!=-1&&step>min_step) return; else if(i==c&&j==d)//到达目的地 { min_step = step;//发现更少步数的解 return;//起码这一层递归是停了 } else if(i>=1&&i<=8&&j>=1&&j<=8&&board[i][j]==0) { board[i][j] = 1; try_step(i - 2, j - 1, step + 1); try_step(i - 2, j + 1, step + 1); try_step(i - 1, j - 2, step + 1); try_step(i - 1, j + 2, step + 1); try_step(i + 1, j - 2, step + 1); try_step(i + 1, j + 2, step + 1); try_step(i + 2, j - 1, step + 1); try_step(i + 2, j + 1, step + 1); //在递归的出口回溯 board[i][j] = 0; } } int main() { cin >> a >> b >> c >> d; try_step(a, b, 0); if(min_step==-1) cout << -1 << endl; else cout << min_step << endl; return 0; }
bfs版本
#include#include using namespace std; bool vis[10][10]={0}; struct node { int x, y; int step; node(int x, int y, int step) : x(x), y(y), step(step) {} // 构造函数 }; int dx[8] = {1, 1, -2, -2, 2, 2, -1, -1}; int dy[8] = {2, -2, 1, -1, 1, -1, 2, -2}; queue q; int bst_search(int a, int b, int c,int d) // BST 作为动态查找(搜索)算法 { if (a == c && b == d) return 0; q.push(node(a,b,0)); vis[a][b] = true; while (!q.empty()) { node t = q.front(); q.pop(); for (int i = 0; i < 8; i++) { int x = t.x + dx[i]; int y = t.y + dy[i]; if (x == c && y == d) { return t.step + 1; } else if (x >= 1 && x <= 8 && y >= 1 && y <= 8 && !vis[x][y]) { //在棋盘上但是没有访问 q.push(node(x,y,t.step+1)); vis[x][y] = true; } } } return -1; //如果跳不到,就返回-1; } int main() { int a, b, c, d; cin >> a >> b >> c >> d; cout << bst_search(a, b, c, d); return 0; }
下边是直接入队不用node结构体的一种策略
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)