Блог

Главная - Вопросы по программированию - В 2D массиве (8×8), как вы рекурсивно печатаете последовательные номера из начальной позиции в конечную позицию?

В 2D массиве (8×8), как вы рекурсивно печатаете последовательные номера из начальной позиции в конечную позицию?

#java #arrays #recursion

#java #массивы #рекурсия

Вопрос:

Задан 2D массив размером 8×8. Пользователь вводит случайное начальное местоположение и случайное конечное местоположение. В Java программа должна генерировать последовательные номера (начиная с 0 для начальной позиции) вплоть до конечной позиции. Для начала узел вверх вниз слева или справа от начального местоположения превратится в 1. Тогда узлы вверх вниз слева или справа от единиц превратятся в 2, если они пусты.

Я пробовал вложенные циклы для генерации чисел и не смог охватить всю матрицу. Я думаю, что рекурсия здесь сработала бы хорошо, но я не очень хорошо разбираюсь в написании рекурсивных задач. Я рассмотрел возможность сначала инициализировать всю матрицу в 0, затем ввести пользователем начальное местоположение в S и конечное местоположение в E. Затем внутри цикла while числа будут генерироваться до тех пор, пока end (E) не станет другим символом / числом.

В этом сценарии я не менял End (E) на число или Start (S) на число, чтобы было проще визуализировать.

 4    3    2    3    4    5    0    0   
3    2    1    2    3    4    5    0   
2    1    S    1    2    3    4    5   
3    2    1    2    3    4    5    0   
4    3    2    3    4    5    0    0   
5    4    3    4    5    E    0    0   
0    5    4    5    0    0    0    0   
0    0    5    0    0    0    0    0

Комментарии:

1. Неясно, чего вы хотите. Ваше описание звучит так, как будто вам нужен один путь от начала до конца, но в примере показаны концентрические круги. Что это? И что вы пробовали до сих пор?

2. Я хочу концентрические круги от начала до конца, которые помогут указать путь в будущем. Желаемый результат — последовательные числа вплоть до конечного местоположения.

3. Почему бы не использовать расширенный цикл for?

Ответ №1:

Это можно сделать с помощью вложенных циклов.

Хитрость заключается в том, чтобы распознать, что вы создаете концентрические ромбы из последовательных чисел, например, 3-й шаг:

       3           yDelta = -3   xDelta =  0
    3   3         yDelta = -2   xDelta = ±1
  3       3       yDelta = -1   xDelta = ±2
3     S     3     yDelta =  0   xDelta = ±3
  3       3       yDelta =  1   xDelta = ±2
    3   3         yDelta =  2   xDelta = ±1
      3           yDelta =  3   xDelta =  0

Это может быть сделано с помощью одного цикла, считая yDelta от -3 до 3 ,

и вычисление xDelta = ±(3 - abs(yDelta))

Код

 private static void printDistances(int width, int height, int xStart, int yStart, int xEnd, int yEnd) {
    // Build clear board
    String[][] board = new String[height][width];
    for (int i = 0; i < height; i  )
        Arrays.fill(board[i], ".");

    // Mark start and end locations
    board[yStart][xStart] = "S";
    board[yEnd][xEnd] = "E";

    // Add distances (steps) from start location until end location reached
    int endStep = Math.abs(xEnd - xStart)   Math.abs(yEnd - yStart);
    for (int step = 1; step < endStep; step  ) {
        String stepValue = String.valueOf(step);
        for (int dy = -step; dy <= step; dy  ) {
            int y = yStart   dy;
            if (y >= 0 amp;amp; y < height) {
                int dx = step - Math.abs(dy);
                if (xStart - dx >= 0 amp;amp; xStart - dx < width)
                    board[y][xStart - dx] = stepValue;
                if (dx != 0 amp;amp; xStart   dx >= 0 amp;amp; xStart   dx < width)
                    board[y][xStart   dx] = stepValue;
            }
        }
    }

    // Print the board
    for (int y = 0; y < height; y  ) {
        for (int x = 0; x < width; x  ) {
            if (x != 0)
                System.out.print(" ");
            System.out.printf("%2s", board[y][x]);
        }
        System.out.println();
    }
}

Пример 1

 printDistances(8, 8, 2, 2, 5, 5);
  
  4  3  2  3  4  5  .  .
 3  2  1  2  3  4  5  .
 2  1  S  1  2  3  4  5
 3  2  1  2  3  4  5  .
 4  3  2  3  4  5  .  .
 5  4  3  4  5  E  .  .
 .  5  4  5  .  .  .  .
 .  .  5  .  .  .  .  .

Пример 2

 printDistances(20, 10, 19, 6, 2, 3);
  
  .  .  .  .  .  . 19 18 17 16 15 14 13 12 11 10  9  8  7  6
 .  .  .  .  . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5
 .  .  .  . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4
 .  .  E 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3
 .  . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2
 . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  S
 . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
 .  . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2
 .  .  . 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3