我给了2个数组,输入和输出数组.目标是通过将给定步骤中的1值移位到其相邻元素,将输入数组转换为输出数组.例如:输入数组为[0,0,8,0,0],输出数组为[2,0,4,0,2].这里第一步是[0,1,7,0,0],第二步是[0,1,6,1,0],依此类推.
什么算法可以有效地做到这一点？我在考虑执行BFS,但后来我们必须从每个元素做BFS,这可能是指数级的.有谁能建议解决这个问题？
我认为 BFS 确实可以工作。
\n\n请注意n*O(n+m)= O(n^2+nm)，因此不是指数。
您还可以使用：Floyd-Warshall 算法和 Johnson\xe2\x80\x99s 算法，对于“平坦”图，权重为 1，甚至可以通过顶点的实际距离以新的方式连接顶点，并可能节省一些迭代。
\n\n希望有帮助:)
\n