复制的旧列表引用被 python 中的新列表对象修改更改

Question

我正在解决这个问题：http://codeforces.com/contest/540/problem/C

这似乎是在坐标平面上的标准广度优先搜索，所以本质上，您可以水平或垂直移动，每次移动都会用字符'X'更新新位置的单元格

为了解决它，我必须创建一个所有可能的相邻状态对象的列表，其中一个 'State' 对象保存一个位置和一个二维数组（坐标 plane/matrix）。我在下面的 'getAdjacentStates' class 函数中创建了这个相邻 'State' 对象的列表：

class State(object):

def __init__(self, matrix, curPosition):
    self.curMatrix = matrix
    self.curPosition = curPosition

def __hash__(self):
    hash = 0
    mult = 1
    for row in range(len(self.curMatrix)):
        for col in range(len(self.curMatrix[0])):
            if(self.curMatrix[row][col] == 'X'):
                hash += mult * 1
            mult*=2
    return hash

def __eq__(self, other):
    for i, row in enumerate(other.curMatrix):
        for j, col in enumerate(other.curMatrix[0]):
            if not(self.curMatrix[i][j] == other.curMatrix[i][j]):
                return False
    return True


#adjacentStates
def getAdjacentStates(self):
    #calculate a new matrix from curMatrix based on horizontal and vertical position movements
    #curMatrix & curPosition

    adjStates = list()

    if(self.curPosition.column > 0):
        # Subtract one from the column of the current position
        leftPos = Position(self.curPosition.row, self.curPosition.column - 1)
        adjStates.append(createState(self.curMatrix, leftPos))

    if(self.curPosition.column < len(self.curMatrix[0]) - 1):
        # Add one to the column of the current position
        rightPos = Position(self.curPosition.row, self.curPosition.column + 1)
        adjStates.append(createState(self.curMatrix, rightPos))

    if(self.curPosition.row > 0):
        # Subtract one from the current position's row
        downPos = Position(self.curPosition.row-1, self.curPosition.column)
        adjStates.append(createState(self.curMatrix, downPos))

    if(self.curPosition.row < len(self.curMatrix) - 1):
        # Add one to the row of the current position
        upPos = Position(self.curPosition.row + 1, self.curPosition.column)
        adjStates.append(createState(self.curMatrix, upPos))
    #print()
    return adjStates

具有附加功能：

def createState(stateMatrix, position):
    newMatrix = list()
    newMatrix = [stateMatrix[row] for row in range(len(stateMatrix))]
    newMatrix[position.row][position.column] = 'X'
    return State(newMatrix, position)

这一切都可以在正确的方向上导航，但是当我打印出具有给定初始状态的相邻状态列表时：

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

我得到了 3 个相同的：

.X..
...X
X.X.
..X.
.XXX

.X..
...X
X.X.
..X.
.XXX

.X..
...X
X.X.
..X.
.XXX

尽管它应该看起来像这样：

.X..
...X
X.X.
....
.XX.

.X..
...X
X.X.
....
.XXX

.X..
...X
X.X.
..X.
.XX.

不介意走上 'X'

的瑕疵

在比较它应该是什么和我得到的东西时，出于某种原因，相邻的 State 对象都有指向公共 'curMatrix' 字段的指针。我不知道为什么，因为在我的 'createState' 函数中，我创建了一个完全独立的列表对象和 return 一个新的 State 对象。

如果有人能就如何解决这个问题提供一些建议，我将非常感谢 python 的初学者帮助，谢谢！

完整代码如下：

import queue

class Position(object):
    def __init__(self, row, column):
        self.row = row
        self.column = column


def createState(stateMatrix, position):
    newMatrix = list()
    newMatrix = [stateMatrix[row] for row in range(len(stateMatrix))]
    newMatrix[position.row][position.column] = 'X'
    return State(newMatrix, position)

class State(object):

    def __init__(self, matrix, curPosition):
        self.curMatrix = matrix
        self.curPosition = curPosition

    def __hash__(self):
        hash = 0
        mult = 1
        for row in range(len(self.matrix)):
            for col in range(len(self.matrix[0])):
                if(self.matrix[row][col] == 'X'):
                    hash += mult * 1
                mult*=2
        return hash

    def __eq__(self, other):
        for i, row in enumerate(other.curMatrix):
            for j, col in enumerate(other.curMatrix[0]):
                if not(self.curMatrix[i][j] == other.curMatrix[i][j]):
                    return False
        return True


    #adjacentStates
    def getAdjacentStates(self):
        #calculate a new matrix from curMatrix based on horizontal and vertical position movements
        #curMatrix & curPosition
        adjStates = list()
        if(self.curPosition.column > 0):
            # Subtract one from the column of the current position
            leftPos = Position(self.curPosition.row, self.curPosition.column - 1)
            adjStates.append(createState(self.curMatrix, leftPos))
        if(self.curPosition.column < len(self.curMatrix[0]) - 1):
            # Add one to the column of the current position
            rightPos = Position(self.curPosition.row, self.curPosition.column + 1)
            adjStates.append(createState(self.curMatrix, rightPos))

        if(self.curPosition.row > 0):
            # Subtract one from the current position's row
            downPos = Position(self.curPosition.row-1, self.curPosition.column)
            adjStates.append(createState(self.curMatrix, downPos))

        if(self.curPosition.row < len(self.curMatrix) - 1):
            # Add one to the row of the current position
            upPos = Position(self.curPosition.row + 1, self.curPosition.column)
            adjStates.append(createState(self.curMatrix, upPos))
        #print()
        return adjStates



    #isFinalState

    def __repr__(self):
        for i, row in enumerate(self.curMatrix):
            for j, col in enumerate(self.curMatrix[i]):
                print(self.curMatrix[i][j], end='')
            print()



n, m = list(map(int, input().split()))
startMatrix = [list(input()) for x in range(n)] #startMatrix[row][column]
startRow, startColumn = list(map(int, input().split()))
startPos = Position(startRow-1, startColumn-1)
endRow, endColumn = list(map(int, input().split()))
endPos = Position(endRow-1, endColumn-1)

initialState = createState(startMatrix, startPos)

testAdj = initialState.getAdjacentStates()
for adj in testAdj:
    adj.__repr__()
    print()

Answer 1

实际上，您在 adjStates.append(createState(self.curMatrix, xxxPos))

中使用相同的列表

def createState(stateMatrix, position):
    newMatrix = list()
    newMatrix = [stateMatrix[row] for row in range(len(stateMatrix))]
    newMatrix[position.row][position.column] = 'X'
    return State(newMatrix, position)

我想你需要原始列表的副本，所以将上面的代码更改为：

def createState(stateMatrix, position):
    # it is superfluous code, so I've just commented it
    # newMatrix = list()

    # Here is the change - create copies of all source lists
    # newMatrix = [list(stateMatrix[row]) for row in range(len(stateMatrix))]
    # But there is a simpler way - iterate direct through list items:
    newMatrix = [list(row) for row in stateMatrix]
    newMatrix[position.row][position.column] = 'X'
    return State(newMatrix, position)

复制的旧列表引用被 python 中的新列表对象修改更改

Copied old list reference being changed by new list object modification in python

python

object

pass-by-reference

pass-by-value

multidimensional-array