Почему мой код не работал правильно в этой задаче
проблема перемещения по сетке
она в основном проблема рекурсии, и вот она: проблема перемещения по сетке
и это мое решение:
#include <stdio.h>
#include <string.h>
int gridtravel(int r, int c) {
if (r == 1 && c == 1) return 1;
if (r == 0 || c == 0) return 0;
return gridtravel(r - 1, c) + gridtravel(r, c - 1);
}
int main() {
int r, c;
scanf("%i%i", &r, &c);
printf("%i\n", gridtravel(r, c));
}
но когда я хочу уменьшить временную сложность с помощью такого решения, я получаю неверный результат:
#include <stdio.h>
#include <string.h>
int gridtravel(int r, int c, int arr[][c]) {
if (arr[r][c] != 0) return arr[r][c];
if (arr[c][r] != 0) return arr[c][r];
if (r == 1 && c == 1) return 1;
if (r == 0 || c == 0) return 0;
arr[r][c] = gridtravel(r - 1, c, arr) + gridtravel(r, c - 1, arr);
return arr[r][c];
}
int main() {
int r, c;
scanf("%i%i", &r, &c);
int arr[r][c];
for (int i = 0; i <= r; ++i) {
for (int j = 0; j <= c; ++j) {
arr[i][j] = 0;
}
}
printf("%i\n", gridtravel(r, c, arr));
}
«Размер», который вы указываете при определении массива, - это количество элементов, а не верхний индекс. Таким образом, массив из r элементов имеет индексы от 0 до r - 1 включительно. Все это означает, что вы выходите за пределы своего массива, и это приводит к неопределенному поведению.
Обратите внимание, что тип передаваемого вами VLA меняется при каждом рекурсивном вызове (int arr[][c] отличается от int arr[][c - 1]), хотя он должен быть одинаковым.
arr[c][r] не может быть правильным
Ответы 2
Вот некоторые проблемы:
Ваш код имеет неопределенное поведение, потому что циклы инициализации записываются за конец массива:
for (int i = 0; i <= r; ++i)должно бытьfor (int i = 0; i < r; ++i), аfor (int j = 0; j <= c; ++j)должно бытьfor (int j = 0; j < c; ++j). Вы также можете упростить это какmemset(arr, 0, sizeof(arr)).Кроме того, вы должны передавать размеры массива отдельно от координат ячейки.
Массив должен быть выделен как квадратная матрица, так как вы получаете доступ как к
arr[r][c], так и кarr[c][r].Учитывая то, как вы используете массив кеша, он должен быть выделен еще одной строкой и столбцом.
Вы должны воспользоваться тем фактом, что
gridtravel(1,x)иgridtravel(x,1)оба являются1, еслиxбольше, чем0.
Вот модифицированная версия:
#include <stdio.h>
#include <string.h>
int gridtravel(int r, int c, int n, int arr[][n]) {
if (arr[r][c] != 0) return arr[r][c];
if (arr[c][r] != 0) return arr[c][r];
if (r == 0 || c == 0) return 0;
if (r == 1 || c == 1) return 1;
return arr[r][c] = gridtravel(r - 1, c, n, arr) + gridtravel(r, c - 1, n, arr);
}
int main() {
int r, c;
if (scanf("%i%i", &r, &c) != 2 || r < 1 || c < 1)
return 1;
int n = (r > c) ? r + 1 : c + 1;
int arr[n][n];
memset(arr, 0, sizeof arr);
printf("%i\n", gridtravel(r, c, n, arr));
return 0;
}
Основные проблемы:
- Границы равны
c-1иr-1 - вы не можете поменять местами индекс
cиr - Двумерные массивы не так просты в обращении.
Если вы хотите использовать большой массив, malloc может быть лучше, чем использование стека.
С 2d-массивом вы должны указать размер в качестве параметра
Здесь код с модификацией с помощью printf для отслеживания путешествия
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int gridtravel(int n, int r,int c, int (*arr)[n]){
printf("travel to %d %d\n", r, c);
if (arr[r][c]!=0) return arr[r][c];
if (r==1 && c==1) return 1;
if (r==0 || c==0) return 0;
arr[r][c] = gridtravel(n, r-1, c, arr)+gridtravel(n, r, c-1, arr);
return arr[r][c];
}
int main(){
int r,c;
scanf("%i%i",&r,&c);
int (*arr)[c] = malloc(sizeof(int[r][c]));
memset(arr, 0, r*c*sizeof(int));
printf("%i\n",gridtravel(c, r - 1, c - 1, arr));
free(arr);
}
Пришло время закинуть его в отладчик и выяснить, почему.