如何生成循环矩阵？

Question

我想用 C 或 C++ 生成一个循环矩阵。

对于 n = 3，如何生成下面的矩阵？

1 2 3
8 9 4
7 6 5

Answer 1

我以前做过几次......

伪代码：

min_x = 0;
min_y = 0;
max_x = X;
max_y = Y;

while(!all_fields_filled){

  // move right  -------------------------
  for(i = min_x; i <= max_x; i++){
    array[min_y][i] = fields_number;
    fields_number++;
  }

  min_y++

  // it is important to check that condition after each for
  // (our total field number could be not divided by 4)
  if(filled_fields == fields_amount) break;
  // edn "move right" procedure -----------


  // ETC. for move DOWN, next LEFT and UP
  // remember to increase min_x/min_y and decrease max_y/max_y

}

Answer 2

作为 @Rin 答案的替代方案，您可以考虑按线性顺序存储矩阵，然后在访问它时重新映射索引。如果您使用 C++，则可以通过访问器函数封装此重新映射，例如：

class WierdMatrix
{
public:
    ...

    int get(int x, int y) const
    {
        /* Mapping goes here */
        return M_[x_mapped][y_mapped];
    }
private:
    int M_[3][3];
};

Answer 3

这个问题是在微软笔试中问到的。
因此考虑给出完整的代码。

下面的代码适用于运行时给定的任意数量的行和任意数量的列。
无需对尺寸进行硬编码。

#include <iostream>
using namespace std;

//Prints matrix in Spiral fashion.
void printSpiral(const int& numRows, int& numCols)
{
    int **v = new int*[numRows]; //Allocation for rows
    for(int i = 0; i< numRows; i++)   //Allocation for columns
    {
        v[i] = new int[numCols];
    }
    int curRow = 0, curCol = -1; //for storing current position while moving.
     //Below variables are for remembering boundaries
     //That is already traversed row/column
     int minRowLimit = -1, maxRowLimit = numRows;
     int minColLimit = -1, maxColLimit = numCols;

    int num = 1; //Start filling from 1
     //Total number of elements to be filled
    int totalElements = numRows * numCols; 
    while(1)
    {
        while(curCol < maxColLimit-1)  //Move right
        {
            ++curCol;
            v[curRow][curCol] = num;
            num++;
        }
        if(num > totalElements) break; //Filling completed.
        minRowLimit++;

        while(curRow < maxRowLimit-1) //Move down
        {
            ++curRow;
            v[curRow][curCol] = num;
            num++;
        }
        if(num > totalElements) break; //Filling completed.
        maxColLimit--;

        while(curCol > minColLimit+1)     //Move left
        {
            --curCol;
            v[curRow][curCol] = num;
            num++;
        }
        if(num > totalElements) break; //Filling completed.
        maxRowLimit--;

        while(curRow > minRowLimit+1)  //Move up
        {
            --curRow;
            v[curRow][curCol] = num;
            num++;
        }
        if(num > totalElements) break; //Filling completed.
        minColLimit++;
    }
     //Print the matrix for verification.
    for(int i = 0; i < numRows; i++)
    {
        for(int j=0; j < numCols; j++)
        {
            cout<<v[i][j]<<"\t";
        }
        cout<<endl;
    }

     //Clean up.
    for(int i = 0; i<numRows; i++)
    {
        delete []v[i];
    }
    delete []v;
}

int main()
{
     //Enter rows and columns according to your choice 
     //regarding matrix dimensions.
    int nRows, nCols;
    cout<<"Enter number of rows"<<endl;
    cin>>nRows;
    cout<<"Enter number of cols"<<endl;
    cin>>nCols;
    printSpiral(nRows, nCols);
}

Answer 4

首先将你的矩阵清空。在我的示例中，我在 std::pair 上使用 std::map，但您也可以使用二维数组。我使用 std::map 因为它更容易看到元素何时丢失。

typedef std::pair<int,int> Coordinate;
typedef std::map<Coordinate,int> Matrix;

然后创建一个包含您想要移动的不同方向的集合。
如果先向右移动，则意味着X加1，Y不变。然后我们向下移动，意味着 Y 增加 1 并离开 X。

typedef std::vector<Coordinate> Moves;
Moves moves;
moves.push_back(std::make_pair(1,0));
moves.push_back(std::make_pair(0,1));
moves.push_back(std::make_pair(-1,0));
moves.push_back(std::make_pair(0,-1));

初始化你的起始坐标，它们移动直到到达“边界”。边界可以是边框，也可以是已填充的单元格。

Coordinate currentPosition = std::make_pair(0,0);
int currentValue = 1;
int currentMovePosition = 0;

然后在一个循环中（但我将其作为练习，供您写出来:-)）只需填充矩阵：

matrix[currentPosition] = currentValue;
++currentValue;

并移动到下一个位置;

Coordinate nextPosition = currentPosition;
nextPosition.first += moves[currentMovePosition].first;
nextPosition.second += moves[currentMovePosition].second;

检查 nextPosition 以查看您是否在矩阵之外（nextPosition.first/second < 0 或 >= 矩阵大小）。

如果您仍在矩阵内，请在地图中使用 std::find 来查看该条目是否已被填充：

if (matrix.find(nextPosition)!=matrix.end()) /* valid position */

如果您撞到矩阵的边界或撞到已填充的条目，请采取再次当前位置，增加 currentMovePosition 以更改方向并重试。
如果改变方向，请务必环绕 currentMovePosition。

currentMovePosition = (currentMovePosition + 1) % 4;

继续这样做，直到矩阵完全填满。

要判断矩阵是否完全填充，可以检查所有4个方向是否都移动到已经填充的元素，但更简单的方法是简单地计算填充单元格的数量，如果等于矩阵的大小*大小则停止。

Answer 5

#define N 3

int coords[N*N];

void printn() {
  int i,j;
  for ( i = 0 ; i < N ; i++ ) {
    for ( j = 0 ; j < N ; j++) {
      printf("%2d ",coords[i*N+j]);
    }
    printf("\n");
  }
}

void gennum(int n,int ox,int oy,int lx) {
  int i,j,k,l;
  for ( j = ox; j < n ;j++) {
    coords[ (oy*N)+j ]=  j-ox + lx;
  }

  for ( i = oy+1; i < n ;i++) {
    coords[ (i*N) + n-1 ] = (i-1) -(oy) + (j-ox) + lx;
  }

  for ( l = n-2 ; l >=ox ;l--) {
    coords[ (n-1)*N + l ] = (n-l-2)+ (i-1) -(oy) + (j-ox)  + lx ;
  }

  for ( k = n-2; k >= oy+1 ;k--) {
    coords[ (k*N)+ox ] = (n-k-2)+(n-l-2)+ (i-1) -(oy) + (j-ox) + lx ;
  }
  if ( n > 2 ) {
    gennum(n-1,ox+1,oy+1,(n-k-2)+(n-l-2)+ (i-1) -(oy) + (j-ox) + lx); 
  }
}

int main() {
  memset(coords,0,N*N*sizeof(int));
  gennum(N,0,0,1);
  printn();
  return 0;
}

Answer 6

在“圆形”矩阵中，它的“中间”也是圆形的，
只不过它不是以 1 开头。
所以绕着周边跑并递归。

void    cmat_step( int** M, int a, int i, int j, int dim)
{    
int    k;
    /* fill perimeter */
    for( k=0; k<dim; ++k)        M[i][j+k]       = a++;
    for( k=1; k<dim; ++k)        M[i+k][j+dim-1] = a++;
    for( k=dim-2; k>=0; --k)     M[i+dim-1][j+k] = a++;
    for( k=dim-2; k>=1; --k)     M[i+k][j]       = a++;
    if ( dim >=2)    
    {    /* fill middle */
        cmat_step( M, a, i+1,  j+1, dim-2);
    }
}
void    cmat( int** M, int dim)    {    cmat_step( M, 1, 0, 0, dim);    }