算法趣题-Q08
2021/9/14 1:05:06
本文主要是介绍算法趣题-Q08,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、问题描述
二、问题分析
如题干所描述的这种寻路问题可以直接用深度遍历来解决,那么,在这题的难点上就是如何判断这个机器人是否走过了本节点,即如何记录机器人走过的路径。我能想到的就有两种:一种是直接构建一个足够大的二维数组,用数组记录路径,在移动次数较多时会有较大的空间开销;另一种是用坐标数组存储路径,有较好的空间复杂度。这两种方法就类似于存储稀疏矩阵的方法。
三、代码实现
1.C/C++实现
#include <iostream> #define MAX_X 25 #define MAX_Y 25 using namespace std; int goNext(int matrix[MAX_X][MAX_Y], int x, int y, int step) { // 因为是数组所以要进行边界检查 if (x > 24 || x < 0 || y > 24 || y < 0 || (matrix[x][y] == 1)) { return 0; } else if (step == 0) { return 1; } else { matrix[x][y] = 1; int temp[MAX_X][MAX_Y]; memcpy(temp, matrix, sizeof(temp)); matrix[x][y] = 0; return goNext(temp, x + 1, y, step - 1) + goNext(temp, x - 1, y, step - 1) + goNext(temp, x, y + 1, step - 1) + goNext(temp, x, y - 1, step - 1); } } int main() { // 地面矩阵,为 1 则走过,为 0 没走过 // 初始位置为 matrix[12][12] int matrix[MAX_X][MAX_Y]; memset(matrix, 0, sizeof(matrix)); cout << goNext(matrix, 12, 12, 12) << endl; return 0; }
2.Python实现
# coding=utf-8 def go_next(x, y, step, path): if (x, y) in path: return 0 elif step == 0: return 1 else: path.append((x, y)) return go_next(x + 1, y, step - 1, path[:]) + go_next(x - 1, y, step - 1, path[:]) + go_next(x, y + 1, step - 1, path[:]) + go_next(x, y - 1, step - 1, path[:]) if __name__ == '__main__': print(go_next(0, 0, 12, []))
这篇关于算法趣题-Q08的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30我的第一个Go命令行工具
- 2024-09-30初学者指南:轻松掌握模块化编程
- 2024-09-30顶级5款免费的IntelliJ插件,助你Java开发之路更顺畅
- 2024-09-30提高应用程序可用性:冗余和持久性
- 2024-09-30Twitter 系统设计面试示例
- 2024-09-30JSON对象入门教程:轻松掌握基础用法
- 2024-09-30封装入门:Java面向对象编程的第一步
- 2024-09-30后台交互入门:轻松掌握基础知识与实践技巧
- 2024-09-30轻松入门:后台交互教程详解
- 2024-09-30后台交互项目实战:新手指南