Created
March 17, 2016 07:18
-
-
Save jianminchen/7d775438e2d0d316f77d to your computer and use it in GitHub Desktop.
Matrix Spiral Print - one variable
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace MatrixSpiralPrint | |
{ | |
/* | |
* Matrix Spiral Print | |
* N - how many columns | |
M - how many rows | |
Actually, there is only one variable, which is i, from 0 to (N+1)/2, N is how many columns in the matrix | |
Four corner: LT, LR, BR, BL | |
LT coordinates: (i, i) | |
LR coordinates: (i, N-1-i) | |
BR coordinates: (M-1 -i, N-1-i) | |
BL coordinates: (M-1-i, i) | |
To test the correctness, just use i = 0; | |
And then, you only need to design a function to iterate through | |
private static void leftToRight(Coordinate[] A) | |
TopToDown, RightToLeft, and DownToUp | |
i | |
0 1 2 | |
--------------> | |
1 2 3 4 5 | |
6 7 8 9 10 | |
11 12 13 14 15 | |
16 17 18 19 20 | |
The above case, LT = (0,0), LR = (0, 4), BR = (3, 4), BL = (3, 0) | |
*/ | |
public class Coordinate | |
{ | |
public int x, y; | |
public Coordinate(int x1, int y1) | |
{ | |
this.x = x1; | |
this.y = y1; | |
} | |
} | |
class Program | |
{ | |
/* | |
* https://msdn.microsoft.com/en-us/library/2s05feca.aspx | |
* int[][] jaggedArray3 = | |
{ | |
new int[] {1,3,5,7,9}, | |
new int[] {0,2,4,6}, | |
new int[] {11,22} | |
}; | |
*/ | |
static void Main(string[] args) | |
{ | |
int[][] A = { | |
new int[]{1, 2, 3, 4,5}, | |
new int[]{6, 7, 8, 9, 10}, | |
new int[]{11, 12, 13, 14, 15}, | |
new int[]{16, 17, 18, 19, 20} | |
}; | |
IList<int> list = matrixSpiralPrint(A); | |
} | |
public static IList<int> matrixSpiralPrint(int[][] A) | |
{ | |
IList<int> output = new List<int>(); | |
if (A.Length == 0) return null; | |
int M = A.Length; // row | |
int N = A[0].Length; // column | |
// LT, LR, BR, BL | |
for(int i =0; i< (N+1)/2; i++) // bug001 - count 13 twice | |
{ | |
if(( i== (N+1)/2 -1) && (M< N)) | |
continue; | |
/* | |
LT coordinates: (i, i) | |
LR coordinates: (i, N-1-i) | |
BR coordinates: (M-1 -i, N-1-i) | |
BL coordinates: (M-1-i, i) | |
* */ | |
// LT, LR, BR, BL | |
Coordinate[] B = { | |
new Coordinate(i, i), | |
new Coordinate(i, N-1-i), | |
new Coordinate(M-1 -i, N-1-i), | |
new Coordinate(M-1-i, i) | |
}; | |
// Left to right | |
leftToRight(A, B[0], B[1], output); | |
topToDown(A, B[1], B[2], output); | |
rightToLeft(A, B[2], B[3], output); | |
bottomToUp(A, B[3], B[0], output); | |
} | |
return output; | |
} | |
private static void leftToRight(int[][] A, Coordinate start, Coordinate end, IList<int> output) | |
{ | |
int row = start.x; | |
for (int i = start.y; i <= end.y; i++) | |
output.Add(A[row][i]); | |
} | |
private static void topToDown(int[][] A, Coordinate start, Coordinate end, IList<int> output) | |
{ | |
int col = start.y; | |
for (int i = start.x +1; i <= end.x; i++) // do not count top point | |
output.Add(A[i][col]); | |
} | |
private static void rightToLeft(int[][] A, Coordinate start, Coordinate end, IList<int> output) | |
{ | |
int row = start.x; | |
for (int i = start.y - 1; i >= end.y; i--) // do not print the start point - Top To Down already handles | |
output.Add(A[row][i]); | |
} | |
private static void bottomToUp(int[][] A, Coordinate start, Coordinate end, IList<int> output) | |
{ | |
int col = start.y; | |
for (int i = start.x - 1; i > end.x; i--) // do not print the start point - Top To Down already handles | |
output.Add(A[i][col]); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment