如何在二维列表中找到一个 2x2 的对象？

Question

我有一个必须完成的练习才能上学，但我有点卡住了。我必须编写一个函数来告诉你照片上是否有一张脸，通过照片我们可以想象一个二维列表，一个由更多列表组成的列表来创建一个二维对象。人脸由 2x2 正方形表示，其中包含单词 face，这些字母可以随机排列。如下图一、二：

也可以有更多的脸，只要face这个词在整个2Dlist中至少出现一次就应该return True.

问题是字母不能排成一行或一列，如图 III 所示。我真的不知道如何制定条件来消除这种情况。到目前为止，我知道如何找出所有字母是否都在该 2D 列表中，并且我消除了只有一行或一列的可能性，如图 IV 所示。和 V..

这是我目前的情况：

def is_face_on_photo(photo):
    list2D = photo
    faces = ['f','a','c','e']
    newlist = []
    for list in list2D:
        for letter in list:
            newlist.append(letter)
    if 'f' in newlist and 'a' in newlist and 'c' in newlist and 'e' in newlist and (faces not in list2D) and (len(list2D) >= 2) and (len(list2D[0]) >= 2):
        print True
    else:
        print False
 pass

我是 python 的新手，所以如果能得到任何帮助，我将不胜感激 :) 非常感谢

Answer 1

逐个元素搜索每一行，然后是下一行，依此类推，从左到右，然后向下，直到找到 F、A、C 或 E。

当您这样做时，由于您是从左到右和从上到下检查，您可以假设您已经找到潜在 "FACE" 的左上角。所以检查右边的字母，下面的字母，右下的字母是否满足剩下的FACE

如果是这样，您就完成了。如果没有，请继续。

编辑： 这是一个有点冗长的版本。我还没有测试过，但就是这个想法。

def is_face_on_photo(photo):
    found = False

    for row,photo_row in enumerate(photo):
        for col,letter in enumerate(photo_row):

            if (letter in "face") and col + 1 < len(photo_row) and row + 1 < len(photo):
                found = True  # Until proven otherwise

                num_found = {"f":0, "a":0, "c":0, "e":0}

                right_letter = photo_row[col + 1]
                below_letter = photo[row + 1][col]
                below_right_letter = photo[row + 1][col + 1]

                letters = [letter, right_letter, below_letter, below_right_letter]

                # Could replace with something like defaultdict
                for let in letters:
                    if let in num_found:
                        num_found[let] += 1

                # Would need to change this slightly if the letters of "face" had 
                # any repetitions, like two "a"s or something
                for let in "face":
                    if num_found[let] == 0:
                        found = False
                        break

            if found:
                break

        if found:
            break

    return found

Answer 2

使用与其他答案中描述的方法有点相似的方法，这里是一个应该有效的实现。它将遍历每个单元格，如果该单元格包含 'face' 中的字母，它将继续检查右侧的三个单元格、下方的三个单元格以及它位于右上角的方格。

请注意，这不是执行此操作的最有效方法：不会保留以前尝试的信息（这可以防止大多数此类尝试）。

def is_face_on_photo(arr):
    word = set('face')
    num_rows = len(arr)
    num_cols = len(arr[0])
    for y, row in enumerate(arr):
        for x, cell in enumerate(row):
            if cell in word:
                # horizontal?
                if x + 3 < num_cols and set(row[x:x+4]) == word:
                    return True
                # vertical
                if y + 3 < num_rows and set(arr[i][x] for i in range(y, y + 4)) == word:
                    return True
                # square
                if x + 1 < num_cols and y + 1 < num_cols and set(arr[y][x:x+2] + arr[y+1][x:x+2]) == word:
                    return True
    return False

    arr = [
        ['x', 'x', 'x', 'x'],
        ['x', 'f', 'c', 'x'],
        ['x', 'a', 'e', 'x'],
        ['x', 'x', 'x', 'x']
    ]

    print (is_face_on_photo(arr)) # True

Answer 3

这是一种扫描二维列表的方法。

我们使用内置的 zip function to get pairs of adjacent rows from the photo, and use zip again to get pairs of adjacent cells from the current pair of rows. This gives us the 4 cells in a 2x2 square. We also use the built-in enumerate 函数为我们提供当前 2x2 正方形左上角的 x,y 索引。

我们将正方形中的字母放入一个集合中，以便我们可以快速测试它是否等于包含 'face' 字母的集合。但我们还需要确保我们找到的任何面孔都不会与我们已经找到的面孔重叠。为此，我们维护一个集合 found 来跟踪我们找到的每张面孔的 x、y 索引。

更新

这是此代码的更好版本；以前的版本不处理同时包含重叠面孔和非重叠面孔的照片。此版本维护另一组 bad，用于跟踪与其他面重叠的面。

all_data = [
    [
        ['x', 'x', 'x', 'x'],
        ['x', 'f', 'a', 'x'],
        ['x', 'c', 'e', 'x'],
        ['x', 'x', 'x', 'x'],
    ],
    [
        ['c', 'a', 'x', 'x'],
        ['f', 'e', 'x', 'x'],
        ['x', 'x', 'x', 'x'],
        ['x', 'x', 'x', 'x'],
    ],
    [
        ['c', 'a', 'f', 'x'],
        ['f', 'e', 'c', 'x'],
        ['x', 'x', 'x', 'x'],
        ['x', 'x', 'x', 'x'],
    ],
    [
        ['c', 'a', 'f', 'x'],
        ['f', 'e', 'c', 'x'],
        ['x', 'c', 'e', 'x'],
        ['x', 'f', 'a', 'x'],
    ],
    [
        ['x', 'a', 'x', 'x'],
        ['f', 'e', 'x', 'x'],
        ['x', 'x', 'x', 'x'],
        ['x', 'x', 'x', 'x'],
    ],
    [
        ['c', 'a', 'x', 'x', 'x', 'x'],
        ['f', 'e', 'c', 'a', 'f', 'e'],
        ['f', 'e', 'e', 'f', 'a', 'c'],
        ['a', 'c', 'x', 'x', 'x', 'x'],
    ],
]

def show(a):
    print('\n'.join(''.join(row) for row in a))

face = set('face')

def is_face_on_photo(photo):
    ''' Return the number of valid faces found in photo '''
    found = set()
    bad = set()
    # Get pairs of adjacent rows
    for y, (row0, row1) in enumerate(zip(photo, photo[1:])):
        # Get pairs of adjacent cells from the pair of rows
        for x, t in enumerate(zip(row0, row0[1:], row1, row1[1:])):
            if set(t) == face:
                found.add((x, y))
                # See if it overlaps any existing faces
                newbad = found.intersection({(x-1, y), (x, y-1), (x-1, y-1)})
                if newbad:
                    bad.update(newbad)
                    bad.add((x, y))
    return len(found) - len(bad)

for photo in all_data:
    show(photo)
    print(is_face_on_photo(photo), '\n')

输出

xxxx
xfax
xcex
xxxx
1 

caxx
fexx
xxxx
xxxx
1 

cafx
fecx
xxxx
xxxx
0 

cafx
fecx
xcex
xfax
1 

xaxx
fexx
xxxx
xxxx
0 

caxxxx
fecafe
feefac
acxxxx
4

如何在二维列表中找到一个 2x2 的对象？

How to find a 2x2 object in a 2D list?

python

list

face-detection

更新