神解

思路
这个问题要求计算在无限方格矩阵上行走n步的不同方案数，每次只能向北、东、西三个方向移动，且走过的格子不能重复。通过动态规划的思路，我们可以将状态分为三个方向：北（N）、东（E）、西（W）。每一步的选择取决于前一步的方向，从而避免重复路径。

​状态定义：设 prev_N、prev_E、prev_W 分别表示上一步向北、东、西方向移动的方案数。

​状态转移：
current_N（当前向北）：可以从任何方向转移而来。
current_E（当前向东）：只能从北或东转移而来。
current_W（当前向西）：只能从北或西转移而来。

​初始状态：当 n=1 时，三个方向各有1种方案。
​递推计算：通过循环递推每一步的状态，直到计算到第n步。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 1 << endl;
        return 0;
    }
    long long prev_N = 1, prev_E = 1, prev_W = 1;
    for (int i = 2; i <= n; ++i) {
        long long current_N = prev_N + prev_E + prev_W;
        long long current_E = prev_N + prev_E;
        long long current_W = prev_N + prev_W;
        prev_N = current_N;
        prev_E = current_E;
        prev_W = current_W;
    }
    cout << prev_N + prev_E + prev_W << endl;
    return 0;
}