Вася каждый день поднимается по одной и той же лестнице. одним шагом он может встать на следующую ступеньку или перешагнуть через одну ступеньку. он уже знает, сколькими он может подняться на верхнюю ступеньку. но недавно он обнаружил, что некоторые ступеньки обветшали, и ступать на них небезопасно. он составил список таких ступенек, и теперь интересуется, сколькими можно подняться по лестнице, не наступая на эти ступеньки.
входные данные
в первой строке вводится одно натуральное число n (n ≤ 40): количество ступенек.
во второй строке вводится одно натуральное число k (k ≤ n): количество опасных ступенек.
в третьей строке вводятся k различных натуральных чисел в диапазоне от 1 до n: номера опасных ступенек.
выходные данные
выведите одно число: количество попасть на n-ю ступеньку.
примеры
входные данные
10
3
5 1 2
выходные данные
0
входные данные
3
1
2
выходные данные
1
#include <iostream>
using namespace std;
int data[20][20], x, y, minValue = -1;
void calc(int px, int py, int value){
value += data[px][py];
int temp = data[px][py];
if(px == x - 1 && py == y - 1) {
if(value < minValue || minValue == -1)
minValue = value;
return;
}
data[px][py] = -1;
if(px + 1 < x && data[px + 1][py] != -1) calc(px + 1, py, value);
if(py + 1 < y && data[px][py + 1] != -1) calc(px, py + 1, value);
data[px][py] = temp;
}
int main(){
cin >> x >> y;
for (int i = 0; i < x; ++i)
for (int j = 0; j < y; ++j)
cin >> data[i][j];
calc(0, 0, 0);
cout << minValue;
return 0;
}
Объяснение:
Я сделал это задание с рекурсии. Функция бесконечно вызывает сама себя и ищет наиболее оптимальный вариант. Фактически это просто подбор, но более сложно реализованный.
P. s. Если Вам ответ, отметьте его как лучший и жмякните на " " . Это мотивирует продолжать давать ответы дальше.
#include <cstdio>
#include <algorithm>
using namespace std;
int a[30][30], n, m;
int main() {
scanf(" %d %d", &n, &m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf(" %d", &a[i][j]);
for(int i = 1; i < m; i++) a[0][i] += a[0][i - 1];
for(int i = 1; i < n; i++) a[i][0] += a[i - 1][0];
for(int i = 1; i < n; i++)
for(int j = 1; j < m; j++)
a[i][j] += min(a[i - 1][j], a[i][j - 1]);
printf("%d", a[n - 1][m - 1]);
return 0;
}
Объяснение: