Подсчет возможных координатных ходов с рекурсией

Question

Я пытаюсь написать метод, который выполняет следующее:

public class GridCounting {
    /** Returns the total number of possible routes (paths) from
     * (x,y) to (tx,ty).
     * There are only three valid kinds of moves:
     *  Increment x by one.
     *  Increment x by two.
     *  Increment y by one.
     *
     *  Hint: You'll need to two base cases.
     */
    public static int count(int x,int y, int tx, int ty) {
        if (x==tx && y==ty)
            return 1;
        if (x>tx || y>ty)
            return 0;
        if (x<tx)
            return 1 + count(x+1, y, tx, ty);
        if (x<tx) //if x is still less, then we can do another move
            return 1 + count(x+2, y, tx, ty);
        if (y<ty){
            return 1 + count(x, y+1, tx, ty);
        }
        return 0;
    }
}

Проблема, с которой я сталкиваюсь, заключается в том, что меня всегда отключает +1.Он ожидает 4, но я даю его 5. Запутывающая часть в том, что если я добавлю счет функции (10,15,10,15), то это все равно будет считаться как 1 ход.Я не знаю, как объяснить это.

Также y ++, тогда x ++ считается за 1 ход, а x ++, затем y ++ - как еще один ход.Редактировать: Фиксированный код:

public static int count(int x,int y, int tx, int ty) {
    if (x==tx && y==ty)
        return 1;
    if (x>tx || y>ty)
        return 0;
    if (x<tx)
        return count(x+1, y, tx, ty) + count(x+2, y, tx, ty) + count(x,y+1,tx,ty);
    if (y<ty) {
        return count(x, y+1, tx, ty); // what does this do?
    }
    return 0;
}

Answer 1

Беда в том, что я всегда на +1. Ожидает 4, но я даю 5.
В позиции (x, y) у нас, вообще говоря, есть три варианта (x+=1, x+=2, y+=1). Каждый из них создает отдельные пути, и нам нужно выяснить, сколько всего путей.
Итак, эта часть неверна

        if (x<tx)
            return 1+ count(x+1, y, tx, ty);
        if (x<tx)
            return 1+ count(x+2, y, tx, ty);
        if (y<ty){
            return 1+ count(x, y+1, tx, ty);
        }
        return 0;

Это был намек, дайте мне знать, если вам нужно больше.

Также y ++, тогда x ++ считается за 1 ход, а x ++, затем y ++ - как еще один ход.
Ну, для меня это звучит как два разных пути.

1020 * редактировать *
Хорошо, return count(x + 1, y, tx, ty) + count(x + 2, y, tx, ty) + count(x, y + 1, tx, ty); - это все, что вам нужно.
Если есть 3 пути, начинающиеся с первого хода x + 1, 2 пути, начинающиеся с первого хода x + 2, и 2 пути, начинающиеся с первого хода y + 1, то, очевидно, всего 3 + 2 + 2 путей.

Answer 2

if (x==tx && y==ty) return 1; не звучит правильно. Если вы уже в пункте назначения, больше нет маршрутов.

Answer 3

Может быть, я не понимаю правила, но я думаю, что это первый базовый случай, который вызывает вашу проблему.Если вы уже на месте, значит, вы не делаете ход.

Answer 4

Вы уверены, что эта строка правильная?

if (x==tx && y==ty)
  return 1;

Кажется, она должна вернуть ноль

На телефоне, поэтому я не могу его проверить.