PHP - создать спираль

При условии, что у меня есть $rows = 4, а также $cols = 4;Как создать массив из 16 элементов в спиральном порядке, например:

1, 2, 3, 4,
12,13,14,5,
11,16,15,6,
10,9, 8, 7,
Источник

3 ответа

Мое решение довольно многословно, потому что вы хотите изучить его и узнать, как оно работает.

<?php
/**
 * Creates a 2D array with the given dimensions,
 * whose elements are numbers in increasing order
 * rendered in a 'spiral' pattern.
 */
function createSpiral($w, $h) {
   if ($w <= 0 || $h <= 0) return FALSE;

   $ar   = Array();
   $used = Array();

   // Establish grid
   for ($j = 0; $j < $h; $j++) {
      $ar[$j] = Array();
      for ($i = 0; $i < $w; $i++)
          $ar[$j][$i]   = '-';
   }

   // Establish 'used' grid that's one bigger in each dimension
   for ($j = -1; $j <= $h; $j++) {
      $used[$j] = Array();
      for ($i = -1; $i <= $w; $i++) {
          if ($i == -1 || $i == $w || $j == -1 || $j == $h)
             $used[$j][$i] = true;
          else
             $used[$j][$i] = false;
      }
   }

   // Fill grid with spiral
   $n = 0;
   $i = 0;
   $j = 0;
   $direction = 0; // 0 - left, 1 - down, 2 - right, 3 - up
   while (true) {
      $ar[$j][$i]   = $n++;
      $used[$j][$i] = true;

      // Advance
      switch ($direction) {
         case 0:
            $i++; // go right
            if ($used[$j][$i]) { // got to RHS
               $i--; $j++; // go back left, then down
               $direction = 1;
            }
            break;
        case 1:
           $j++; // go down
           if ($used[$j][$i]) { // got to bottom
               $j--; $i--; // go back up, then left
               $direction = 2;
            }
            break;
         case 2:
            $i--; // go left
            if ($used[$j][$i]) { // got to LHS
               $i++; $j--; // go back left, then up
               $direction = 3;
            }
            break;
         case 3:
            $j--; // go up
            if ($used[$j][$i]) { // got to top
               $j++; $i++; // go back down, then right
               $direction = 0;
            }
            break;
       }

       // if the new position is in use, we're done!
       if ($used[$j][$i])
           return $ar;
   }
}

/**
 * Assumes the input is a 2D array.
 */
function print2DGrid($array) {
   foreach ($array as $row) {
       foreach ($row as $col) {
          print sprintf("% 2d ", $col);
       }
       print "\n";
   }
}


$width  = 12;
$height = 8;

print2DGrid(createSpiral($width, $height));
?>

Здесь это в действии, давая следующий вывод:

 0  1  2  3  4  5  6  7  8  9 10 11 
35 36 37 38 39 40 41 42 43 44 45 12 
34 63 64 65 66 67 68 69 70 71 46 13 
33 62 83 84 85 86 87 88 89 72 47 14 
32 61 82 95 94 93 92 91 90 73 48 15 
31 60 81 80 79 78 77 76 75 74 49 16 
30 59 58 57 56 55 54 53 52 51 50 17 
29 28 27 26 25 24 23 22 21 20 19 18

Надеюсь это поможет.

Источник

Используйте вектор и логические значения. Итерируйте по оси X, чтобы начать, пока не дойдете до конца строки. Установите значение true для каждой позиции при ее прохождении. Каждый раз, когда вы достигнете границы или логического значения true, поверните направо.

Таким образом, в первой строке ваш "вектор" будет менять приращение X на ноль, а приращение Y - на 1. Затем вы будете проверять значение приращения на каждом повороте и учитывать 4 сценария.

Это первый способ, о котором я подумал.

Второй способ не использовал бы логические значения, а просто отслеживал бы, сколько столбцов или строк осталось перед курсором на его пути, уменьшая X или Y, оставшиеся на каждом повороте. Остальная логика останется прежней.

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

Вы можете использовать вышеуказанный метод для квадрата любого размера.

Источник

Алгоритм не очень сложен. Вы должны повторить от 1 вплоть до $rows*$cols, Во время итерации необходимо рассчитать положение текущего числа в матрице ($x,$y), Первый на будет в (1,1) конечно. Следующий будет ($x+1,$y) потому что ты едешь на восток. Таким образом, позиция каждого числа основывается на позиции предыдущего и правильном направлении.

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

В общем, это будет ~30 строк кода PHP.

Надеюсь, это поможет.

Аналогичная проблема в PHP-гольфе: http://www.phpgolf.org/challenge/Spiral. Кто-то решил это всего за 130 символов!

Источник
Другие вопросы по тегам