给定一个二维数组，我想以蜗牛模式遍历它并使用一个循环打印出元素。
例如，如果给定的数组是：
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
所以从左上角开始，到达阵列的中心。
这是一个 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;
}
我们可以用一个周期来完成，而无需存储额外的矩阵。以下代码假定您可以使用 C++11 中的std::vector，并且基于极客的极客示例。当然，该算法也可以在没有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;
}
}
}
以下是在 Javascript 中实现它的方法
snail = function(arr) {
let [y, x] = [0, 0];
let [rs, ls, us, ds] = [0, 0, 0, 0]
let [xLimit, yLimit] = [arr.length, arr.length];
let dir = 'right'
const res = []
const len = arr[0].length * arr[0].length
const rowLen = arr[0].length
while (res.length < len) {
res.push(arr[y][x])
switch (dir) {
case 'right':
if (x + 1 < xLimit) {
x++
} else {
dir = 'down'
yLimit = rowLen - ds
rs++
y++
}
break;
case 'down':
if (y + 1 < yLimit) {
y++
} else {
dir = 'left'
xLimit = ls
ds++
x--
}
break;
case 'left':
if (x > xLimit) {
x--
} else {
dir = 'up'
yLimit = ds
ls++
y--
}
break;
case 'up':
if (y > yLimit) {
y--
} else {
dir = 'right'
xLimit = rowLen - rs
us++
x++
}
break;
default:
break;
}
}
return res
}
它没有使用任何内置的Javascript函数，因此可以翻译成任何语言。
以下是您问题的简单解决方案：
-
保留一个与数组大小相同(所有单元格初始化为
0(的 2D 数组(checkIfVisited(，以便跟踪已经访问过的单元格。如果(i,j)1则表示已访问原始单元格中的单元格。 -
我们在
dir变量的帮助下螺旋迭代整个数组，该变量跟踪我们当前正在遍历的方向。 2表示向上移动，3表示向左移动。当
i和j超出限制时，或者当之前已经通过从checkIfVisited数组中查找来遍历下一个要遍历的单元格时，我们会改变方向。
dir = 0表示向下移动，1表示向右移动，我有上述算法的简单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