'''
Given a 2D array, print it in spiral form.

Input:     {{1,    2,   3,   4},
            {5,    6,   7,   8},
            {9,   10,  11,  12},
            {13,  14,  15,  16 }}

Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
'''


dir_sequence = [0, 1, 2, 3] # 0: right, 1: down, left: 2, left : 3

class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def get_next_dir(cur_dir, dir_sequence):
    return cur_dir + 1 if cur_dir + 1 < len(dir_sequence) else 0

def get_next_pos(cur_pos, dir):
    
    next_x = cur_pos.x
    next_y = cur_pos.y

    # right
    if dir == 0:
        next_x +=1
    # doown
    elif dir == 1:
        next_y += 1
    # left
    elif dir == 2:
        next_x -= 1
    # up
    elif dir == 3:
        next_y -= 1
    else:
        raise Exception("invaild direction. {}".format(dir))
    return Pos(next_x, next_y)

def can_move(cur_pos, dir, visited, max_pos):
    next_pos = get_next_pos(cur_pos, dir)

    if 0 <= next_pos.x and next_pos.x <= max_pos.x and 0 <= next_pos.y and next_pos.y <= max_pos.y:
        return visited[next_pos.y][next_pos.x] == False
    return False

def dfs(cur_pos, max_pos, direction, visited, input):

    # first print out the current pos
    print(input[cur_pos.y][cur_pos.x], end=" ")
    visited[cur_pos.y][cur_pos.x] = True

    next_dir = direction
    if can_move(cur_pos=cur_pos, dir=direction, visited=visited, max_pos=max_pos) != True:
        next_dir = get_next_dir(cur_dir=direction, dir_sequence=dir_sequence)
        if can_move(cur_pos=cur_pos, dir=next_dir, visited=visited, max_pos=max_pos) != True:
            return
    next_pos = get_next_pos(cur_pos=cur_pos, dir=next_dir)
    dfs(cur_pos=next_pos, max_pos=max_pos, direction=next_dir, visited=visited, input=input)

def print_spiral(width, height, input):

    visited = [[ False for i in range(width)] for j in range(height)]
    initial_pos = Pos(0, 0)
    max_pos = Pos(width - 1, height - 1)

    initial_dir = 0

    dfs(initial_pos, max_pos, initial_dir, visited, input)

# test cases


input= [
    [1,    2,   3,   4],
    [5,    6,   7,   8],
    [9,   10,  11,  12],
    [13,  14,  15,  16]
]

print_spiral(4, 4, input)

# expected output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10