切片结构使用太多内存

Question

I tried to solve this problem with BFS, but for input "99 100" my program uses more than 260 Mb and online-judge system throws MEMORY_LIMIT_EXCEEDED. I guess the problem is the way I use QUEUE. So what do you think is the problem? And how should I solve it?

Here is my code. And thanks in advance!:

package main

import (
    "fmt"
)

type pair struct {
    nn int
    dd int
}

func main() {
    var n, m int
    fmt.Scanf("%d%d", &n, &m)

    if n >= m {
        fmt.Println(n - m)
    } else {
        device := make([]pair, 1)
        device[0] = pair{n, 0}

        ans := 0
        for {
            // pop front element
            tmp := device[0]
            device = device[1:]

            if tmp.nn == m { // reached destination
                ans = tmp.dd
                break
            }

            // add neighbors to the queue
            device = append(device, pair{tmp.nn - 1, tmp.dd + 1})
            device = append(device, pair{tmp.nn * 2, tmp.dd + 1})
        }

        fmt.Println(ans)
    }
}

EDIT: More readable and working(ACCEPTED) code:

package main

import (
    "fmt"
)

type pair struct {
    location int
    dist     int
}

func main() {
    var n, m int
    fmt.Scanf("%d%d", &n, &m)

    if n >= m {
        fmt.Println(n - m)
    } else {
        visited := make([]bool, m+2)

        queue := make([]pair, 1)
        queue[0] = pair{n, 0}

        ans := 0
        visited[n] = true
        for {
            // pop front element
            tmp := queue[0]
            queue = queue[1:]

            // reached destination
            if tmp.location == m {
                ans = tmp.dist
                break
            }

            // add neighbors to the queue
            if tmp.location*2 <= m+1 && visited[tmp.location*2] == false {
                queue = append(queue, pair{tmp.location * 2, tmp.dist + 1})
                visited[tmp.location*2] = true
            }
            if tmp.location-1 >= 0 && visited[tmp.location-1] == false {
                queue = append(queue, pair{tmp.location - 1, tmp.dist + 1})
                visited[tmp.location-1] = true
            }
        }

        fmt.Println(ans)
    }
}

Answer 1

Your algorithm is not BFS, because, you can visit the same state more than one.

For example, 4 -> 3 -> 6 and 4 -> 8 -> 7 -> 6, which 6 will end up to be processed twice.

Secondly, for number x that is greater than the target, the minimum number of step is always

x - target + step to reach x

so you should not add it into the queue.

By doing those two modifications, the space complexity will be limited to O(m) which should help you to solve the problem.

Sample code

ans := -1
dist := make([]int, m + 1)
q := make([]int,1)
q[0] = n

for i := 0; i < len(q); i++ {
    node := q[i]
    if node == m {
       if ans == -1 || ans > dist[m]{
          ans = dist[m]
       }
       break;
    }
    a := node*2
    b := node - 1
    if a >= m {
       if ans == -1 || ans > (1 + dist[node] + a - m) {
          ans = 1 + dist[node] + a - m
       }
    }else if dist[a] == 0 && a != n {
       q = append(q, a)
       dist[a] = 1 + dist[node]
    }
    if dist[b] == 0 && b != n {
       q = append(q, b)
       dist[b] = 1 + dist[node]
    } 
}
return ans