[数据结构与算法]算法趣题-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, []))