如何在c++中制作数字顺时针旋转的二维数组

Question

我需要在c++中创建一个顺时针旋转的二维数组，如下所示:

789
612
543

问题是我没有找到一个好的算法。

我试着改变x和y，每次都改变索引，但我该如何改变x和y呢?

例如:

int num[1001][1001];
int n = 1;
int x = 0;
int y = 0;
for (int i = 500; i < 1001 && i >= 0; i++)
{
    for (int j = 500; j < 1001 && j >= 0; i++)
    {
        num[i + x][j + y] = n;
    }
}

Answer 1

设n = 2k + 1为数组的维数

设s为螺旋数，s=0为中心(1)。

那么每个螺旋需要5个循环:

iterating from [k+1,k+1+s] to [k+1+s,k+1+s]
from [k+1+s,k+1+s-1] to [k+1+s,k+1-s]
from [k+1+s-1,k+1-s] to [k+1-s,k+1-s]
from [k+1-s,k+1-s+1] to [k+1-s,k+1+s]
from [k+1-s+1,k+1+s] to [k,k+1+s]

我可能在这里犯了一个错误，但是大意应该会有帮助。

后来

我已经添加了完整的程序，但这里螺旋继续，而不是上面给出的索引界。

#include <iostream>
#include <iomanip>
static const int k = 3;
static const int n = 2*k+1;
int a[n][n];
void set(int r, int c, int v){
  a[r-1][c-1] = v;
}
void dump(){
  for( int r = 0; r < n; r++ ){
    for( int c = 0; c < n; c++ ){
      std::cout << std::setw( 3 ) << a[r][c];
    }
    std::cout << std::endl;
  }
}
int main(){
  int v = 2;
  set( k+1,k+1,1);
  for( int s = 1; s <= k; s++ ){
    for( int r = k+1-s+1; r <= k+1+s; r++ ) set( r, k+1+s, v++ );
    for( int c = k+1+s-1; c >= k+1-s; c-- ) set( k+1+s, c, v++ );
    for( int r = k+1+s-1; r >= k+1-s; r-- ) set( r, k+1-s, v++ );
    for( int c = k+1-s+1; c <= k+1+s; c++ ) set( k+1-s, c, v++ );
  }
  dump();
  //...

}

在k设置为2的情况下运行该命令产生:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

Answer 2

试一个简单的例子，你有一个数组的如下开头:

   7  8  9 10
   6  1  2 11
   5  4  3 12
17 16 15 14 13

如果你在移动中思考它，就会出现一个模式:

1 right
1 down
2 left
2 up
3 right
3 down
4 left
...

什么是move?

right = +0 row +1 col
left = +0 row -1 col
up = -1 row +0 col
down = +1 row +0 col

所以现在你所需要做的就是遵循这个简单的算法，直到你达到一个退出条件。

int size = 4 //or 5?
bool notReachedTheEnd = true;
std::vector<std::vector<int>> grid(std::vector<int>(0, size), size);
int row = (size-1)/2;
int col = row;
int counter = 1;
int movenumber = 1;
int movedamount = 0;
enum states = {LEFT, RIGHT, UP, DOWN};
states state = RIGHT;
while (notReachedTheEnd)
{
    grid[row][col] = counter++;  //Assign the current grid cell
        //Handle moves
        switch state
        {
            case LEFT:
                col--;
                movedamount++;
                if (movedamount == movednumber)
                {
                    movedamount = 0;
                    case = UP;
                }
            case RIGHT:
                row++;
                movedamount++;
                if (movedamount == movednumber)
                {
                    movedamount = 0;
                    case = DOWN;
                }
            case UP:
                row--;
                movedamount++;
                if (movedamount == movednumber)
                {
                    movedamount = 0;
                    movecount++;
                    case = RIGHT;
                }
            case DOWN:
                row++;
                movedamount++;
                if (movedamount == movednumber)
                {
                    movedamount = 0;
                    movecount++;
                    case = LEFT;
                }
          }
          //Now check exit condition
          if (row >= size || col >= size)
          {
                 break;
          }
    }                                         

这是未编译的未检查代码，但它是解释解决此问题的方法的好方法。

希望这对你有帮助。