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

Question

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

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

为了解决这个问题，我必须创建一个所有可能相邻状态对象的列表，其中一个“状态”对象拥有一个位置和一个二维数组（坐标平面/矩阵）。我在下面的“getAdjacentState”类函数中创建相邻“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

我得到三个相同的：

.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'函数中，我创建了一个完全独立的list对象并返回一个新的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)