Question

问一道c++题

4、 迷宫 （ chess.cpp/c/pas）
【问题描述】
晚上，跑男们来了节目的最后一站：江苏省扬州中学，完成最后一项比赛：撕名牌。 撕名牌的地点是
一个由 n*n 房间组成的正方形，每个房间里都有一个数字，表示从这个房间可以通过地道向右或向下穿过
几个房间。 从左上角开始，如果谁能安全到达右下角就算胜利。
这里 4*4 的方格中每一格表示进入这个房间时，队员可以向右或向下穿过的房间数。
郑恺是奔跑小王子， 当他拿到这张地图时， 脸都变绿了，速度再快，进了迷宫一样的房间也是没办法
啊，还好参加 JSOI2015 夏令营的小伙伴都在，你能帮帮他算出从左上角可以到达右下角的路径数目吗？
【输入】
输入文件名为 chess.in。
第一行为一个整数 n，表示棋盘的大小。
以下有 n 行，每行有 n 个数字（数字与数字之间有一个空格隔开），表示在相应的格子内，棋子可以
向右或向下跳跃的格子数。
【输出】
输出文件名为 chess.out。
输出共一行，包含一个数，表示从左上角可以到达右下角的路径数目。
【输入输出样例】
chess.in chess.out
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

3
我的代码：
#include <iostream>
#include <fstream>
using namespace std;
int a[109][109];
ifstream fin("chess.in");
ofstream fout("chess.out");
void dfs(int n,int i,int j){
int s=0;
if(i==n&&j==n) s++;
else {
if(j+a[i][j]<=n) dfs(n,i,j+a[i][j]);
if(i+a[i][j]<=n) dfs(n,i+a[i][j],j);
}
fout<<s;
return;
}
int main(){
int n;
fin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
fin>>a[i][j];
dfs(n,1,1);
return 0;
}

请问哪里错了

Answer 1

递归函数的退出条件有问题。
在做向下递归时，按照你的写法，只要上级走到某个点，那么就必然会输出一个路径数量。这就意味着你可能会输出很多次。但事实上是，只需要输出一次就够了。另一个问题就是，你的路径计数是临时变量，那么每次都是从0开始的。这当然也是不对的。