C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-07-12 20:08:07

#include <iostream>
int n,a[9][9];
bool V[751];
int ans;
void DFS(int x,int y,int v)
{
	v += a[x][y];
	if (x < n)
		DFS(x + 1,y,v);
	if (y < n)
		DFS(x,y + 1,v);
	if (x == n && y == n)
	{
		ans += ! V[v],V[v] = 1;
	}
}
main()
{
	std::cin >> n;
	for (int i = 1;i <= n;++ i)
		for (int j = 1;j <= n;++ j)
			std::cin >> a[i][j];
	DFS(1,1,0);
	std::cout << ans << '\n';
}

C++ 解法, 执行用时: 4ms, 内存消耗: 416K, 提交时间: 2022-02-22 21:39:43

#include<bits/stdc++.h>
using namespace std;
set<int>s;
int i,j,n,a[10][10];
void dfs(int i,int j,int sum){
    if(i==n||j==n)return;
    sum+=a[i][j];
    if(i==n-1&&j==n-1)s.insert(sum);
    dfs(i+1,j,sum);
    dfs(i,j+1,sum);
}
int main(){
    cin>>n;
    for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>a[i][j];
    dfs(0,0,0);
    cout<<s.size();
}

Python3(3.5.2) 解法, 执行用时: 56ms, 内存消耗: 3476K, 提交时间: 2019-07-14 16:24:15

n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))


path = [] #不同的路径

def dp(num,i,j):
    num+=a[i][j]
    if i==n-1 and j==n-1 and (num not in path) :
        path.append(num)
        return 0
    if(i<n-1):
        dp(num,i+1,j);
    if(j<n-1):
        dp(num,i,j+1);
    
dp(0,0,0)
print(len(path))