如何以蜗牛模式单次循环遍历二维数组？

Question

给定一个二维数组，我想以蜗牛模式遍历它并使用[=打印出元素21=]一个单周期.

例如，如果给定的数组是：

10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34

程序应该打印出：

10 15 20 25 30 31 32 33 34 29 24 19 14 13 12 11 16 21 26 27 28 23 18 17 22

所以从左上角开始，到达数组的中心

Answer 1

这里有一个简单的解决方法：

保留一个与您的数组大小相同的二维数组 (checkIfVisited)（所有单元格都初始化为 0），以便跟踪那些单元格已经访问过。如果(i,j)是1那么说明原来的单元格已经被访问过
我们在 dir 变量的帮助下螺旋迭代整个数组，该变量跟踪我们当前遍历的方向。
dir = 0表示向下移动，1表示向右移动，2表示向上移动，3表示移动向左.
当 i 和 j 超出限制时，或者当要遍历的下一个单元格之前已经通过从 checkIfVisited数组.

我有上述算法的简单 C++ 实现：

#include <iostream>
using namespace std;
int main() 
{
    int arr[5][5] = {10, 11, 12, 13, 14,
                     15, 16, 17, 18, 19,
                     20, 21, 22, 23, 24,
                     25, 26, 27, 28, 29,
                     30, 31, 32, 33, 34};

    int checkIfVisited[5][5] = {0,0,0,0,0,
                                0,0,0,0,0,
                                0,0,0,0,0,
                                0,0,0,0,0,
                                0,0,0,0,0};
    int i,j,dir,countVisited;
    dir = 0;
    countVisited = 0;
    i = 0;
    j = 0;
    while(countVisited<5*5)
    {
        cout<<arr[i][j]<<" ";
        checkIfVisited[i][j]=1;
        if(dir==0)
        {
            countVisited++;
            if(i+1>4 || checkIfVisited[i+1][j]==1){
                dir=1;
                j++;
            }
            else
                i++;
        }
        else if(dir==1)
        {
            countVisited++;
            if(j+1>4 || checkIfVisited[i][j+1]==1){
                dir=2;
                i--;
            }
            else
                j++;
        }
        else if(dir==2)
        {
            countVisited++;
            if(i-1<0 || checkIfVisited[i-1][j]==1){
                dir=3;
                j--;
            }
            else
                i--;
        }
        else
        {
            countVisited++;
            if(j-1<0 || checkIfVisited[i][j-1]==1){
                dir=0;
                i++;
            }
            else
                j--;
        }
    }

    return 0;
}

输出： 10 15 20 25 30 31 32 33 34 29 24 19 14 13 12 11 16 21 26 27 28 23 18 17 22

Answer 2

我们可以在不存储额外矩阵的情况下用一个循环来完成。以下代码假定您可以使用 C++11 中的 std::vector，并且基于 geeks for geeks 中的示例。当然，该算法在没有 std::vector 的情况下也能正常工作。此外，这只蜗牛是顺时针方向的，作为练习，您应该将其更改为逆时针方向:)。 [我没有编译代码]

#include <iostream>
#include <vector>

using namespace std;

void printSnail(vector<vector<int>> const &matrix)
{
  size_t nRow = matrix.size();       // Number of rows that are not printed yet
  size_t nCol = matrix[0].size();    // Number of columns that are not printed yet

  size_t k = 0;
  size_t l = 0;

  // Print all elements in the matrix
  while (k < nRow and l < nCol)
  {
    // Print first row of remaining rows
    for (size_t idx = l; idx < nCol; ++idx)
      cout << matrix[k][idx] << ' ';
    ++k;

    // Print last column of remaining columns
    for (size_t idx = k; idx < nRow; ++idx)
      cout << matrix[idx][nCol - 1] << ' ';
    --nCol;

    // Print last row of remaining rows
    if (k < nRow)
    {
      for (size_t idx = nCol - 1; idx >= l; --idx)
        cout << matrix[nRow - 1][idx] << ' ';
      --nRow;
    }

    // Print the first column of the remaining columns
    if (l < nCol)
    {
      for (size_t idx = nRow - 1; idx >= k; --idx)
        cout << matrix[idx][l] << ' ';
      ++l;
    }
  }
}

Answer 3

这是一个for循环的解决方案：

仅当矩阵为：n >= m

时有效

#include <iostream>

using namespace std;

int main()
{
//    int arr[4][3] = {{0, 9, 8} , {1, 10 , 7} , {2, 11, 6} , {3, 4, 5}};
//    int n = 4, m = 3;

    int arr[4][4] = {{0, 11, 10, 9} , {1, 12, 15, 8} , {2, 13, 14, 7} , {3, 4, 5, 6}};
    int n = 4, m = 4;

    int row = 0, col = 0, turn = 0;
    bool isTop = true;

    for(int nrElem = 0; nrElem <= (n*m); nrElem++)
    {
        //This part make the left, bottom, right part ( U form )
        if((row < n-1-turn) && (col != m-1) && (isTop == true))
        {
            cout << " " << arr[row][col];
            row++;
        } else {
            if((row == n-1-turn) && (col < m-1-turn))
            {
                cout << " " << arr[row][col];
                col++;
            } else {
                if((col == m-1-turn) && (row > 0))
                {
                    cout << " " << arr[row][col];
                    row--;
                } else {
                    isTop = false;
                }
            }
        }
        //

        //And this do the top backward parsing
        if((col > 0) && (isTop == false))
        {
            cout << " " << arr[row][col];
            col--;
        } else {
            if (isTop == false)
            {
                isTop = true;
                turn++;
                row += turn;
                col += turn;
            }
        }
    }

    cout << endl;
    return 0;
}

如何以蜗牛模式单次循环遍历二维数组？

How can I iterate through a two-dimensional array in a snail mode, with a single cycle?

arrays

algorithm

matrix

multidimensional-array

cycle