В этом коде, в рекурсии находится ошибка, которую я никак не могу найти. Помогите, пожалуйста!
вот ссылка на задачу, которую я решаю 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;
}
Другие языки программирования и технологии
задачка на c++
А почему в условии 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;
}
}
Полагаю, ваше решение и идея этого решения изначально неверны. Значит искать и исправлять в нем ошибки бесполезно.
Рекурсивная функция должна подсчитывать минимальные суммы, а у вас она занимается какой-то фигней.
#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;
}
}
попробуйте без рекурсии, ведь есть множество замечательных алгоритмов нахождения кратчайшего пути (в вашем случае это минимальная сумма) 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
Похожие вопросы
- помогите сделать задачку на c++ пожалуйста.
- C++ ( решите задачку )
- Программисты C#, помогите. задачка элементарная
- c++ задачка про одномерный статический массив
- задачка про массив C++
- Подскажите учебник по C++! Подскажите учебник по С++, с самого нуля. Желательно с примерами и задачками!
- C# Помогите решить задачку.
- C++ ЗАДАЧКА, ПОМОГИТЕ ПЛИЗ
- Учусь програмировать на C++ по книге "C++ для чайников".Проблема.
- Помогите решить задачку простенькую.