using System;

class Solution
{
    public static List<int> Spiral(int[,] matrix)
    {
        List<int> res = new List<int>();
        if(matrix==null)
            return res;
        int[,] dir = new int[4,2] {{0,1},{1,0},{0,-1},{-1,0} };

        int rows = matrix.GetLength(0);
        int cols = matrix.GetLength(1);

        if(rows ==0 || cols==0)
            return res;

        int top=0,bottom= rows-1,left=0,right=cols-1;

        int total =rows*cols;
        int k=0;
        int x=0,y=0;
        res.Add(matrix[x,y]);
        total--;

        while(total>0)
        {
            int newX = x + dir[k,0];
            int newY = y + dir[k,1];

            //check valididty
            if(newX >=top && newX <=bottom && newY >=left && newY <=right)
            {
                x = newX;
                y=newY;
                res.Add(matrix[x,y]);
                total--;
            }
            else
            {
                switch(k)
                {
                    case 0:
                        top++;
                        break;
                    case 1:
                        right--;
                        break;
                    case 2:
                        bottom--;
                        break;
                    case 3:
                        left++;
                        break;
                }

                k = (k+1)%4;
            }

            return res;
        }
    }

    static void Main(string[] args)
    {
        for (var i = 0; i < 5; i++)
        {
            Console.WriteLine("Hello, World");
        }
    }
}