Python solution inspired by Turtle Graphics


  • 0

    I just recalled a very old programming practice that you enter commands and the turtle will draw lines to form a graph. The key is when to change directions. In this problem, when the turtle is out of bound or visit a visited node, it should be reset to the previous position and change to another direction.
    alt text

    class Solution(object):
        def generateMatrix(self, n):
            """
            :type n: int
            :rtype: List[List[int]]
            """
            if n < 1:
                return list()
            res = [[1] * n for x in range(n)]
            visited = [[0] * n for x in range(n)]
            visited[0][0] = 1
            dirs = [[0,1],[1,0],[0,-1],[-1,0]] # right,down,left,up
            i,j,i_pre,j_pre = 0,0,0,0
            cnt = 0
            k = 2
            while k <= n*n:
                i,j = i+dirs[cnt % 4][0],j+dirs[cnt % 4][1]
                if i < 0 or j < 0 or i>n-1 or j>n-1 or visited[i][j] == 1:
                    cnt += 1
                    i,j = i_pre,j_pre
                else:
                    visited[i][j] = 1
                    res[i][j] = k
                    k+= 1
                    i_pre,j_pre = i,j
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.