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

Question

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

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

为了解决这个问题，我必须创建所有可能的相邻 State 对象的列表，其中“State”对象保存一个位置和一个二维数组(坐标平面/矩阵)。我在下面的“getAdjacentStates”类函数中创建了相邻“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 对象都有指向公共(public)“curMatrix”字段的指针。我不知道为什么，因为在我的“createState”函数中，我创建了一个完全独立的列表对象并返回一个新的 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)