БлогNot. Обход матрицы по раскручивающейся спирали

Обход матрицы по раскручивающейся спирали

У меня вчера спирали
Прямо из п***ы украли,
Вот же, ё***ая в рот,
До чего дошёл народ!

(ненародная современная частушка; сей неприличный эпиграф потом уберу, но уж очень к месту - до чего нашёл программистский народ, не могут алгоритма осилить...)

Короче говоря, мы хотим получить нечто вот такое:

  9  8  8  8  8  8  8  8  8 10
  9  7  6  6  6  6  6  6  8 10
  9  7  5  4  4  4  4  6  8 10
  9  7  5  3  2  2  4  6  8 10
  9  7  5  3  1  2  4  6  8 10
  9  7  5  3  1  2  4  6  8 10
  9  7  5  3  3  3  4  6  8 10
  9  7  5  5  5  5  5  6  8 10
  9  7  7  7  7  7  7  7  8 10
  9  9  9  9  9  9  9  9  9 10

(порядок обхода элементов матрицы показан увеличением цифр)

На словах алгоритм очень прост:

1. выбрать начальную точку и направление, шаг step=1;

2. шагнуть на step ячеек в выбранном направлении, повернуть;

3. снова шагнуть на на step ячеек в новом направлении, повернуть, увеличить step на 1;

4. повторить с шага 2.

Код программы-примера на Паскале:

const n=10; {размерность матрицы}
var a:array [1..n,1..n] of integer;
 x,y,dx,dy,step,dir,k,s,count,error:integer;
begin
 for x:=1 to n do {заполнение матрицы нулями}
 for y:=1 to n do a[x,y]:=0;
 x:=n div 2; {текущие координаты в матрице - }
 y:=n div 2; {начинаем с середины}
 step:=1; {сначала шаг будет = 1 элементу}
 dir:=1; {первый шаг будет вниз, можно другие направления}
 k:=0; {дополнительный счётик поворотов}
 count:=0; {счётчик заполненных элементов}
 error:=0; {счётчик лишних шагов}
 repeat
  dx := dir div 10; {смещение по оси x}
  dy := dir mod 10; {смещение по оси y}
  for s:=1 to step do begin {заполнение матрицы}
   if (x>0) and (x<=n) and (y>0) and (y<=n) then begin
    a[y,x]:=step;
    inc(count);
   end
   else inc(error); {если можно, ставим элемент, иначе считаем лишний шаг}
   inc(x,dx); {изменить текущие координаты в матрице}
   inc(y,dy);
  end;
  if dir=10 then dir:=-1 {10 - вправо}
  else if dir=-1 then dir:=-10 {-1 - вверх}
  else if dir=-10 then dir:=1 {-10 - влево}
  else if dir=1 then dir:=10; {1 - вниз}
  inc(k); {считаем, не пора ли повернуть}
  if k=2 then begin inc(step); k:=0; end; {поворот каждые 2 шага}
 until count=n*n; {надо заполнить всю матрицу}
 for x:=1 to n do begin {вывод полученной матрицы}
  writeln;
  for y:=1 to n do write(a[x,y]:3);
 end;
 writeln;
 writeln ('Illegal steps:',error); {вывели число лишних шагов}
 writeln ('Press ENTER to exit');
 readln; {ждем нажатия Enter}
end.

Вот что выходит при первом шаге влево от середины матрицы:

_
  9  9  9  9  9  9  9  9  9 10
  7  7  7  7  7  7  7  7  8 10
  7  5  5  5  5  5  5  6  8 10
  7  5  3  3  3  3  4  6  8 10
  7  5  3  1  1  2  4  6  8 10
  7  5  3  2  2  2  4  6  8 10
  7  5  4  4  4  4  4  6  8 10
  7  6  6  6  6  6  6  6  8 10
  8  8  8  8  8  8  8  8  8 10
 10 10 10 10 10 10 10 10 10 10
Illegal steps:10

То есть, мы прошли с девятками вниз слева от первого столбца. Это потому, что стремимся здесь заполнить всю матрицу (см. условие выхода из цикла).

В качестве альтерантивы условие выхода из цикла можно сделать

until step>=n;
(или >, а не >=) без использования переменной count.

Тогда некоторые начальные значения dir оставят незаполненные строки или столбцы.

В коде примера заполнение всегда будет по спирали, раскручивающейся против часовой стрелки, подумайте, что изменить, чтобы ходить по часовой? Верно, порядок смены направлений вправо-вверх-влево-вниз нужно поменять на вправо-вниз-влево-вверх, то есть, в коде изменится блок выбора следующего направления:

if dir=10 then dir:=1
else if dir=1 then dir:=-10
else if dir=-10 then dir:=-1
else if dir=-1 then dir:=10;

Также понятно, что если нужно заполнять матрицу последовательно возрастающими значениями, просто напишите

a[y,x]:=count;

(а не step) во вложенном цикле for.


теги: алгоритм pascal

11.11.2012, 16:15; рейтинг: 9501