Use Pixel/Grid Walking Simulation to Fill a Spiral Matrix

ACMer

11 years ago

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
1
2
3
4
5
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.
We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column and then we move inwards by 1 and then repeat. That’s all, that is all the simulation that we need.
Think about when you want to switch the progress on one of the indexes. If you progress on
i
out of
[i, j]
, you’d be shifting in the same column. Similarly, by changing values for
j
, you’d be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It’s always best to run the simulation on edge cases like a single column or a single row to see if anything breaks or not.

This puzzle asks you to fill a matrix/grid in a spiral sequence. The input is a vector representing two dimensional array/matrix. The output is also a vector representing the array of spiral sequence. The type of the elements is int. The size of the matrix is known, so the total length of the returning vector can also be computed, equal to m x n if m is the number of rows and n is the number of columns. We can allocate the returning vector in advance or append numbers to the vector on the fly using push_back().

We can start from the top-left corner (which is matrix[0][0]) and start the first direction right, keep walking until either reaching the boundary or the pixel has been visited before. Then try walking downwards, and then left, and upwards. If no possible next valid pixel is found, break the loop (we have completed the matrix).

We use a two dimensional boolean array to mark visited pixels. The C/C++ solution is:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> r;
        int maxx = matrix.size();
        if (maxx == 0) return r;
        int maxy = matrix[0].size();
        int x = 0; 
        int y = 0;
        bool **flag = new bool*[maxx];
        for (int i = 0; i < maxx; i ++) {             
                flag[i] = new bool[maxy];         
        }         
        int dx = 0, dy = 1;         
        for (;;) {             
            r.push_back(matrix[x][y]);             
            // marked as visited             
            flag[x][y] = true;             
            // next pixel valid ?             
            int nx = x + dx;             
            int ny = y + dy;             
            if ((nx >= 0) && (nx < maxx) && (ny >= 0) && (ny < maxy)) {
                // go with the same direction if possible
                if (!flag[nx][ny]) {
                    x = nx;
                    y = ny;
                    continue;
                }
            }
            // try first right
            if ((y < maxy - 1) && (!flag[x][y + 1])) {
                y ++;
                dx = 0;
                dy = 1;
                continue;
            }
            // then down
            if ((x < maxx - 1) && (!flag[x + 1][y])) {                 
                x ++;                 
                dx = 1;                 
                dy = 0;                 
                continue;             
            }                         
            // then left             
            if ((y > 0) && (!flag[x][y - 1]))
            {
                y --;
                dx = 0;
                dy = -1;
                continue;
            }
            // then up
            if ((x >0) && (!flag[x - 1][y]))
            {
                x --;
                dx = -1;
                dy = 0;
                continue;
            }
            // ok finish , can't go one step any more
            break;
        }
        return r;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> r;
        int maxx = matrix.size();
        if (maxx == 0) return r;
        int maxy = matrix[0].size();
        int x = 0; 
        int y = 0;
        bool **flag = new bool*[maxx];
        for (int i = 0; i < maxx; i ++) {             
                flag[i] = new bool[maxy];         
        }         
        int dx = 0, dy = 1;         
        for (;;) {             
            r.push_back(matrix[x][y]);             
            // marked as visited             
            flag[x][y] = true;             
            // next pixel valid ?             
            int nx = x + dx;             
            int ny = y + dy;             
            if ((nx >= 0) && (nx < maxx) && (ny >= 0) && (ny < maxy)) {
                // go with the same direction if possible
                if (!flag[nx][ny]) {
                    x = nx;
                    y = ny;
                    continue;
                }
            }
            // try first right
            if ((y < maxy - 1) && (!flag[x][y + 1])) {
                y ++;
                dx = 0;
                dy = 1;
                continue;
            }
            // then down
            if ((x < maxx - 1) && (!flag[x + 1][y])) {                 
                x ++;                 
                dx = 1;                 
                dy = 0;                 
                continue;             
            }                         
            // then left             
            if ((y > 0) && (!flag[x][y - 1]))
            {
                y --;
                dx = 0;
                dy = -1;
                continue;
            }
            // then up
            if ((x >0) && (!flag[x - 1][y]))
            {
                x --;
                dx = -1;
                dy = 0;
                continue;
            }
            // ok finish , can't go one step any more
            break;
        }
        return r;
    }
};

The running time complexity is O(nm) since we know it takes exactly nm steps (total elements in the matrix) to finish the pixel walking. If you don’t like for(;;) ‘endless loop’, you can remove it by using a fixed-step loop for (int i = 0; i < n * m; i ++).

To generate a spiral matrix given the size: Algorithm to Generate the Spiral Matrix in Clock-wise Order

–EOF (The Ultimate Computing & Technology Blog) —

780 words
Last Post: Print 26 Uppercase Letters using 6502 Assembler on 8-bit Famicom Clone BBG (BBK) - Tutorial 5 - Using Loop
Next Post: C/C++ Coding Exercise - Count and Say - LeetCode Online Judge - Simulation of Number Sequences

The Permanent URL is: Use Pixel/Grid Walking Simulation to Fill a Spiral Matrix (AMP Version)