Я вижу, что никто не использовал только один for loop и без рекурсии в коде, и поэтому я хочу внести свой вклад.
Идея такова:
Представьте, что в точке (0,0) стоит черепаха, то есть в верхнем левом углу, обращенная на восток (вправо)
Она будет продолжать идти вперед , и каждый раз, когда она видит знак, черепаха поворачивает направо
Таким образом, если мы поместим черепаху в точку (0,0), направленную вправо, и если мы разместим знаки в соответствующих местах, черепаха будет пересекать массив по спирали.
Теперь проблема: «Где поставить знаки?»
Давайте посмотрим, куда мы должны поместить знаки (отмеченные # и цифры O):
For a grid that looks like this:
O O O O
O O O O
O O O O
O O O O
We put the signs like this:
O O O #
# O # O
O # # O
# O O #
For a grid that looks like this:
O O O
O O O
O O O
O O O
We put the signs like this:
O O #
# # O
O # O
# O #
And for a grid that looks like this:
O O O O O O O
O O O O O O O
O O O O O O O
O O O O O O O
O O O O O O O
We put the signs like this:
O O O O O O #
# O O O O # O
O # O O # O O
O # O O O # O
# O O O O O #
Мы можем видеть, что, если точка не находится в верхней левой части, знаки являются местами в точках, где расстояния до ближайшей горизонтальной границы и ближайшей вертикальной границы одинаковы , тогда как для верхняя левая часть, расстояние до верхней границы на единицу больше, чем расстояние до левой границы , причем приоритет отдается верхнему правому углу в случае горизонтального центрирования точки и верхнему левому краю в в случае, если точка расположена вертикально по центру.
Это можно легко реализовать в простой функции, взяв минимум (curRow и height-1-curRow), затем минимум (curCol и width-1-curCol) и сравните, если они совпадают. Но нам нужно учесть верхний левый регистр, то есть когда минимум равен curRow и curCol. В этом случае мы соответственно уменьшаем вертикальное расстояние.
Вот код C:
#include <stdio.h>
int shouldTurn(int row, int col, int height, int width){
int same = 1;
if(row > height-1-row) row = height-1-row, same = 0; // Give precedence to top-left over bottom-left
if(col >= width-1-col) col = width-1-col, same = 0; // Give precedence to top-right over top-left
row -= same; // When the row and col doesn't change, this will reduce row by 1
if(row==col) return 1;
return 0;
}
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
void printSpiral(int arr[4][4], int height, int width){
int directionIdx=0, i=0;
int curRow=0, curCol=0;
for(i=0; i<height*width; i++){
printf("%d ",arr[curRow][curCol]);
if(shouldTurn(curRow, curCol, height, width)){
directionIdx = (directionIdx+1)%4;
}
curRow += directions[directionIdx][0];
curCol += directions[directionIdx][1];
}
printf("\n");
}
int main(){
int arr[4][4]= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
printSpiral(arr, 4, 4);
printSpiral(arr, 3, 4);
}
Какие выходы:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
1 2 3 4 8 12 11 10 9 5 6 7