@Gagatyn
Самоучка

Как подсчитать комбинацию шагов коня на матрице 4 на 3?

IS80H.jpg
если плохо видно то вот
Не могу подсчитать шахматные номера на матрице 4 на 3. Не могу сохранить место шага коня и идти от этого шага дальше. Мне нужна рекурсия? Тогда скорее всего нужна функция, не могу понять какие аргументы нужны функции. Если раскомментить строчки в коде, то он покажет верные допустимые шаги на один раз.

int x=0,y=0;
    for(int i=0; i<4;i++) {
        for(int j=0; j<3;j++) {
        x=i;
        y=j;
        a[3][j] = 0;
        cout<<a[i][j]<<endl;
        if (x + t < 4 && y + o < 3) { c++; x=i+t; y=j+o; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x + t < 4 && y - o > -1) { c++; x=i+t; y=j-o; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x + o < 4 && y + t < 3) { c++; x=i+o; y=j+t; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x + o < 4 && y - t > -1) { c++; x=i+o; y=j-t; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x - t > -1 && y + o < 3) { c++; x=i-t; y=j+o; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x - o > -1 && y + t < 3) { c++; x=i-o; y=j+t; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x - t > -1 && y - o > -1) { c++; x=i-t; y=j-o; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
        if (x - o > -1 && y - t > -1) { c++; x=i-o; y=j-t; printf("a[%d][%d] - %d\n", x, y, a[x][y]);  /*x=i;y=j;*/ }
}
}

результат: (уходит в минус, хотя условие не должно позволять)
1
a[2][1] - 8
a[-2][1] - 0
2
a[2][2] - 9
a[1][-1] - 3
a[-1][3] - 1
3
a[2][1] - 8
a[-2][3] - 0
4
a[3][1] - 0
a[-1][1] - 2
5
a[3][2] - 0
a[-1][0] - 0
6
a[3][1] - 0
a[-1][3] - 1
7
a[3][2] - 0
a[0][-1] - 1
8
a[0][2] - 3
9
a[3][0] - 0
a[0][3] - 4
0
a[1][1] - 5
0
a[1][2] - 6
a[2][-1] - 6
0
a[1][1] - 5
  • Вопрос задан
  • 383 просмотра
Решения вопроса 2
@dmitryKovalskiy
программист средней руки
Такие задачи считаются не циклическим перебором, а скорее рекурсивно. к примеру у нас есть точка входа -
мы первым делом перебираем все возможные переходы - получаем следующие 2-3 цифры и по факту имеем еще 2-3 точки входа, от которых считаем все следующие возможные переходы. И так проваливаемся пока не досчитаем до седьмой точки. К Примеру : 1 -6,8; 16 - 7,1 : 18 - 1,3 ; 167 - 2,6 и т.д. пока не получим строчку из 7. Для оптимизации строим двумерный массив одно измерение которого - номера на телефоне, а другое - массив возможных переходов
Ответ написан
https://jsfiddle.net/v7onjy9y/6/
Набросал на js.
Вообще безыдейно тупым перебором собираем все комбинации, потом редьюсим.
На ввод оставил строку и столбец
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Непральный подход.
Нужно создать верный словарь и далее - перебрать все сочетания по словарю.
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
Твоё дело — перебор с кэшированием.
Для каждой кнопки вручную закидываем в массив конских «соседей» — ни одного для 5-ки, три для 4 и 6, два для остальных.
Затем заведи массив 10×7 (стартовая кнопка×длина) и устрой рекурсию с одним небольшим добавлением: если оно закэшировано, брать из кэша. Правила — f(b, 1) = 1, для остальных — sum{c=сосед(b)} f(c, i−1).
Можно и динамическим программированием, без рекурсии — всё равно расход вычислительной мощи незначительный. Сначала f(b, 2), затем f(b, 3), и т.д. до 7.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы