Python DFS and backtracking code beats 100% submissions(69ms)


  • 0
    K

    0_1473044426054_upload-e48143b6-3a39-440b-a018-ef49877e28f6

    def printAns(row, col, ans):
    map = []
    for i in range(len(row)):
    	str = ""
    	for j in range(len(row)):
    		if row[i] == j:
    			str = str + 'Q'
    		else:
    			str = str + '.'
    	map.append(str)
    ans.append(map)
    
    def dfs(row, col, n, ans, t, add, menus):
    if n == 0:
    	printAns(row, col, ans)
    i = t - n
    for j in range(t):
    	if col[j] == -1:
    		a = i + j
    		m = i - j + t
    		if add[a] == 0 and menus[m] == 0:
    			row[i] = j
    			col[j] = i
    			add[a] = 1
    			menus[m] = 1
    			dfs(row, col, n - 1, ans, t, add, menus)
    			add[a] = 0
    			menus[m] = 0
    			row[i] = -1
    			col[j] = -1
    
    class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        row = [-1 for i in range(n)]
    	col = [-1 for i in range(n)]
    	add = [0 for i in range(2*n+1)]
    	menus = [0 for i in range(2*n+1)]
    	ans = []
    	dfs(row, col, n, ans, n, add, menus)
    	return ans

Log in to reply
 

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