如何在單個循環中以蝸牛模式遍歷二維數組？

Question

給定一個二維數組，我想在蝸牛模式中遍歷它，並使用單個循環打印出元素。

例如，如果給定的數組是：

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

下面是一個用於環路的溶液：

它工作，只有當所述基質是：N> =米

#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; 
} 

Answer 2

這裏有一個簡單的解決問題的方法：

• 保持同樣大小的一個二維數組（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 3

我們可以用一個單一的週期做沒有存儲附加矩陣。以下代碼假定您可以使用std::vector從C++11並基於geeks for geeks的示例。當然，該算法也不需要std::vector。此外，這隻蝸牛順時針旋轉，作爲練習，你應該改變它做逆時針:)。 [I沒有編譯代碼]

#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; 
    } 
    } 
}