c++ телефонный номер [требует правки]

218

05 февраля 2018, 05:24

Телефонный номер называют "шахматным", если его цифры набирают на кнопочной панели телефона ходом шахматного коня.

Необходимо составить программу, которая подсчитывает, сколько можно набрать разных "шахматных" номеров с заданным количеством цифр, которые начинаются с заданной цифры.

Ход коня Г-образный на 2 и 1 кнопки, например: с 1 можно перейти на 8 или на 6, а со 2 на 7 или на 9.

Входные данные: два целых числа, разделенных пробелом: n и k, первое из которых задает цифру, с которой будет начинаться телефонный номер, а второе - количество цифр в номере. 0 ≤ n ≤ 9; 1 ≤ k ≤ 12.

Результат: одно число - количество различных "шахматных" номеров длиной k, которые начинаются с цифры n.

Answer 1

Да просто рекурсией. Глубина крайне мелкая, так что не нужно даже никаких изысков типа мемоизации и т.п.

#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;
vector<vector<int>> moves =
{
    {4,6},{6,8},{7,9},{4,8},{3,9,0},{},
    {1,7,0},{2,6},{1,3},{2,4}
};
int count(int last, int n)
{
    if (n == 0) return 1;
    int Sum = 0;
    for(auto k: moves[last])
    {
        Sum += count(k,n-1);
    }
    return Sum;
}

int main()
{
    int n, k;
    cin >> n >> k;
    cout << count(n,k-1) << endl;
}

Answer 2

Вообще выглядит просто (хотя и похожа на олимпиадную). Можно заранее посчитать, какие "ходы" можно сделать с каждой кнопки. Например, с "1" - "8" и "6" (да и со всех 2 варианта, кроме "5", с нее никуда, "4" и "6" - с них по 3). Ну и далее всё просто: задается первая цифра, Вы смотрите, сколько вариантов с нее куда-то прыгнуть и куда именно, далее умножаете и складываете, проходя вглубь. Длина не больше 12, так что, думаю, даже по времени уложитесь.