Посчитать число изломов (углов) у линии, проходящей спиралью по массиву

[BlackFishSQL]

Здравствуйте!
Помогите с задачей, идею подкиньте! ничего путного не лезет в голову
суть в том что дана матрица NxM (любые числа)! сказано что линия начинается в верхнем левом углу (А[1,1]) идёт вдоль первой строки до конца, затем идёт в низ (тоесть по правому крайнему столбику донизу), затем поворачивает влево и идет по самой нижней строке и так она колесит по матрице (получается спираль) и доходит доконца! Нужно определить сколько углов образует эта прямая(красный цвет), угла (синие)

[TinMan]

Как-то вот так..

min:= m;
if m<n then min:= n;
writeln(2*min-2);

Пояснения нужны?

[BlackFishSQL]

Непомешали бы!
p.s. если не трудно!)

[TinMan]

Сообщение от BlackFishSQL

Непомешали бы!
p.s. если не трудно!)

Сорри, я ошибся чуток.. Меня поправили ).
И тот человек сам объяснит тогда
p.s. если не трудно ))

Юля, тебе +1, и сиб!

[+Юлия GaL+]

If n>=m then t:=m*2-1 else t:=n*2-2;

вот решение, объяснения чуть позже будут...

[BlackFishSQL]

Не объясните почему оно именно так?????

[BlackFishSQL]

что никто не поможет разобраться??? вроде код простой а смысл в чём???

[TinMan]

Сообщение от BlackFishSQL

что никто не поможет разобраться??? вроде код простой а смысл в чём???

Хорошо.
Сначала рассмотрим горизонтальную матрицу (то есть столбцов больше, чем строк). Нарисуй ее, как ты рисовал, и проведи спираль, отметив повороты. Потом заметь, что в середине несколько столбцов не содержат ни поворотов, ни начальных или конечных точек. Следовательно, их можно удалить из матрицы, не изменив икомого кол-ва поворотов. Удалишь и увидишь, что матрица стала квадратной. Причем сторона этого квадрата равная количеству строк.

Теперь, если добавлять к этой квадратной матрице один столбец (слева) и одну строку (снизу) и продолжить спираль, а также одновременно повернуть ее на 180 градусов (чтоб начало спирали снова было вверху слева), то мы увидим, что добавилось 2 поворота. Отсюда нетрудно вывести формулу для этого случая.

В этот момент может показаться, что этот ответ будет верен для всех матриц (то есть и для вертикальных тоже), потому что вся картина представляется симметричной. Именно такую ошибку я и сделал, и Юля меня поправила (сиб еще раз!)). Картина на самом деле не совсем симметрична, поскольку есть ДВА параметра, связанных с центральным углом: направление И начало спирали (перед большой строной или перед малой). Но чтобы разобраться нужно проделать то же самое.

Рисуешь вертикальную матрицу и удаляешь все "лишние" строки. Но теперь оказывается, что если не удалять точку окончания спирали, то матрица не дотягивает до квадратной, остается кособокой (строк на 1 больше, чем столбцов). Конечно, окончание спирали - это не поворот, и кажется, что эту строку тоже можно удалить.. Но при попытке это сделать сразу видно, что раз удаляется звено спирали, то исчезает и поворот, так что это делать нельзя. Так что оставляем как есть и считаем повороты, и их оказывается на 1 больше, чем в горизонтальной матрице такого же размера. Дальше все точно так же как - добавляем по одному столбцу и строке и вертим матрицу. Формула та же самая, но плюс 1.

По сути, удаление центральных столбцов и строк не обязательно. Можно просто начать с самой маленькой матрицы (2xN или Mx2) и наращивать ее по одному слою (тем же способом). Кому что удобнее )). Просто удаление центральных строк/столбцов сразу бросается в глаза, и очень хочется его приткнуть )).