Другие языки программирования и технологии

задачка на c++

В этом коде, в рекурсии находится ошибка, которую я никак не могу найти. Помогите, пожалуйста!

вот ссылка на задачу, которую я решаю http://acmp.ru/index.asp?main=task&id_task=368

#include <iostream>

using namespace std;

int d[113][113], n, a[113][113];

char c, ch[113][113];

void rec(int i, int j){

ch[i][j]='#';

if(i!=1&&j!=1||i!=1&&j==1||i==1&&j!=1){

if(d[i-1][j]>d[i][j-1]){

rec(i, j-1);

}else{

rec(i-1, j);

}

}

}

int main(){

//freopen("input.txt","r",stdin);

//freopen("output.txt","w",stdout);

cin>>n;

for(int i=1; i<=n; i++){

for(int j=1; j<=n; j++){

cin>>c;

a[i][j]=c-'0';

d[i][j]=0;

ch[i][j]='.';

}

}

d[1][1]=a[1][1];

for(int i=2; i<=n; i++){

d[i][1]=a[i][1]+d[i-1][1];

d[1][i]=a[1][i]+d[1][i-1];

}

for(int i=2; i<=n; i++){

for(int j=2; j<=n; j++){

d[i][j]=a[i][j]+min(d[i][j-1], d[i-1][j]);

}

}

rec(n, n);

for(int i=1; i<=n; i++){

for(int j=1; j<=n; j++){

cout<<ch[i][j];

}

cout<<endl;

}

// for(int i=1; i<=n; i++){

// for(int j=1; j<=n; j++){

// cout<<d[i][j]<<" ";

// }

//cout<<endl;

// }

return 0;

}
Серёга Шмидт
Серёга Шмидт
1 006
А почему в условии N до 250, а у вас размерность всех массивов только до 113?
Полагаю, ваше решение и идея этого решения изначально неверны. Значит искать и исправлять в нем ошибки бесполезно.
Рекурсивная функция должна подсчитывать минимальные суммы, а у вас она занимается какой-то фигней.

#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

#define N 250

int t[N][N], s[N][N], p[N][N], n;

int f(int i = 0, int j = 0) {
if (s[i][j] == -1) {
if (i == n - 1 && j == n - 1) return s[i][j] = t[i][j];
else if (i == n - 1) return s[i][j] = t[i][j] + f(i, j + 1);
else if (j == n - 1) return s[i][j] = t[i][j] + f(i + 1, j);
else return s[i][j] = t[i][j] + min(f(i, j + 1), f(i + 1, j));
}
return s[i][j];
}

int main() {
int i, j;
ifstream in("input.txt");
in >> n;
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
char c; in >> c;
t[i][j] = c - '0';
}
}
fill(&s[0][0], &s[0][0] + sizeof(s) / sizeof(s[0][0]), -1);
f();
for (i = j = 0; i < n && j < n; ) {
p[i][j] = 1;
if (i == n - 1) ++j;
else if (j == n - 1) ++i;
else if (s[i][j + 1] < s[i + 1][j]) ++j;
else ++i;
}
ofstream out("output.txt");
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) out << (p[i][j] ? '#' : '.');
out << endl;
}
}
Юрий Хворостянный
Юрий Хворостянный
64 626
Лучший ответ
попробуйте без рекурсии, ведь есть множество замечательных алгоритмов нахождения кратчайшего пути (в вашем случае это минимальная сумма) http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B5%D0%BC_%D0%BF%D1%83%D1%82%D0%B8
Миша Онищенко
Миша Онищенко
8 491