Скопированная старая ссылка на список, измененная новой модификацией объекта списка в python

Question

Я работаю над этой проблемой: http://codeforces.com/contest/540/problem/C

Похоже, что это стандартный поиск в ширину по координатной плоскости, поэтому, по сути, вы можете перемещаться по горизонтали или вертикали, обновляя ячейку новой позиции символом "X" при каждом перемещении.

Чтобы решить эту проблему, мне нужно создать список всех возможных смежных объектов State, где объект "State" содержит позицию и 2d массив (координатная плоскость / матрица). Я создаю этот список соседних объектов State в моей функции класса getAdjacentStates ниже:

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.

не обращайте внимания на недостаток при ходьбе на "Х"

По сравнению с тем, что должно быть и что я получаю, по какой-то причине все смежные объекты State имеют указатели на общее поле 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)