Блог

Главная - Вопросы по программированию - лучший способ найти структуру в двумерном списке python

лучший способ найти структуру в двумерном списке python

#python #2d

#python #2d

Вопрос:

У меня есть такой 2d-список:

 [['X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' '],
 ['X', ' ', 'X', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' '],
 ['X', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
 ['X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', 'X', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X'],
 [' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
 [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
 [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']]

Он представляет собой 2d-карту. Есть ли лучший / более эффективный способ найти эту структуру:

 XXX 
X X
X X
XXX

чем это:

 if map[y][x] == map[y][x 1] == map[y][x 2] == map[y 1][x] == map[y 1][x 2] == map[y 2][x] == map[y 2][x 2] == map[y 3][x] == map[y 3][x 1] == map[y 3][x 2] =="X" and map[y 1][x 1] == map[y 2][x 1] == " ":
    return True
else: return False

Комментарии:

1. Как насчет 2 for цикла?

Ответ №1:

Может быть, что-то вроде этого?

 data = [['X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' '], ['X', ' ', 'X', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' '], ['X', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '], ['X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', 'X', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X'], [' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', ' '], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']]

def check_valid(x, y, row, col):
    #check left and right column
    for i in range(row):
        #if out of range or any character is not 'X' then return wrong pattern
        if x   i >= len(data) or data[x   i][y] != 'X':
            return False
   
    #check top and bottom row
    for i in range(col):
        #same as above
        if y   i >= len(data[0]) or data[x][y   i] != 'X':
            return False

    #also we need to check the middle must all be ' '
    for i in range(1, row - 1):
       for j in range(1, col - 1):
           if data[x   row][y   col] != ' ':
               return False

    return True

for x in range(len(data)):
    for y in range(len(data[0])):
        if check_valid(x, y, 4, 3):
            print(x,y)

Вывод:

 0 0
1 11
2 14

Комментарии:

1. Может быть, вы можете немного объяснить это?

2. Первый цикл заключается в проверке левого столбца и правого столбца, второй цикл заключается в проверке верхней строки и нижней строки

3. Что я здесь делаю, так это проверяю для каждой позиции (x, y) из входной матрицы, содержит ли прямоугольник от (x, y) до (x 3, y 2) допустимый шаблон

4. Таким образом, шаблон недействителен, если какой-либо символ в ограничивающей рамке этого прямоугольника не является ‘X’ или прямоугольник не полностью входит в матрицу

5. Редактировать: я просто замечаю, что середина прямоугольника также должна быть заполнена . поэтому я обновил свой ответ, если это не важно, вы можете удалить последнюю часть.