C++且不使用vector头文件完成：从原点出发每一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？输入描述输入文件为stepin包含一个数0N21;输出描述输出文件为stepout一个数表示多少种走法样例1输入1输出3样例2输入2输出7提示0N21

解题思路： 这是一个典型的回溯算法问题。我们可以使用递归的方式来解决。

具体步骤如下：

1. 定义一个全局变量count，用于记录总的走法数。
2. 定义一个二维数组visited，用于标记已经走过的点。
3. 定义一个递归函数backtrack，参数包括当前位置的x和y坐标，以及已经走过的步数step。
4. 在递归函数中，首先判断是否已经走过了N步，如果是，则将count加1。
5. 然后判断当前位置是否合法，即没有越界且没有走过。如果合法，则将该位置标记为已走过，然后分别向右、上、左三个方向递归调用backtrack函数。
6. 最后，将当前位置标记为未走过。
7. 在主函数中，读取输入的N，初始化count和visited数组，然后调用backtrack函数，传入起点(0,0)和步数0。
8. 输出count即为结果。

C++代码如下：

#include #include using namespace std;

int count = 0; int visited[21][21] = {0}; // 记录已经走过的点

void backtrack(int x, int y, int step, int N) { if (step == N) { count++; return; } if (x+1 < 21 && visited[x+1][y] == 0) { // 向右走 visited[x+1][y] = 1; backtrack(x+1, y, step+1, N); visited[x+1][y] = 0; } if (y+1 < 21 && visited[x][y+1] == 0) { // 向上走 visited[x][y+1] = 1; backtrack(x, y+1, step+1, N); visited[x][y+1] = 0; } if (x-1 >= 0 && visited[x-1][y] == 0) { // 向左走 visited[x-1][y] = 1; backtrack(x-1, y, step+1, N); visited[x-1][y] = 0; } }

int main() { ifstream input("step.in"); int N; input >> N; input.close();

backtrack(0, 0, 0, N);

ofstream output("step.out");
output << count << endl;
output.close();

return 0;