Golang DFS


  • 0
    R
    func numberOfPatterns(m int, n int) int {
        skip:= [10][10]int{}
        skip[1][3] = 2
        skip[3][1] = 2
        skip[1][7] =4
        skip[7][1] = 4
        skip[3][9] =6
        skip[9][3] = 6
        skip[7][9] =8
        skip[9][7] = 8
        skip[1][9] =5
        skip[9][1] = 5
        skip[2][8] = 5
        skip[8][2] =5
        skip[3][7] = 5
        skip[7][3] =5
        skip[4][6] = 5
        skip[6][4] = 5
        
        visited := [10]bool{false, false ,false, false, false, false, false, false, false, false}
        result:=0
        
        for i := m; i <= n; i++ {
            result += DFS(visited, skip, 1, i-1) * 4
            result += DFS(visited, skip, 2, i-1) * 4
            result += DFS(visited, skip, 5, i-1)
        }
        
        return result
    }
    
    func DFS(visited [10]bool, skip[10][10]int, current int, remaining int) int {
        if (remaining < 0) {return 0}
        if (remaining == 0) {return 1}
        visited[current] = true
        result := 0
        for i := 1; i <= 9; i++ {
            if !visited[i] && (skip[current][i] == 0 || (visited[skip[current][i]])) {
                result += DFS(visited, skip, i, remaining-1)
            }
        }
        visited[current] = false
        return result
    }
    

Log in to reply
 

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