如何判断100*100矩阵中特定点是否位于字符图形内部？

问题定义 #

需要实现一个布尔函数，输入100×100的字符矩阵（元素为'0'或'1'）和目标坐标(x,y)，判断该点是否处于'1'所构成图形的内部区域（即被'1'完全包围的'0'区域）。

示例1（规则正方形）：

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

此时arr[5][5]（0索引）应返回true，arr[1][1]返回false。

示例2（不规则图形，边厚度变化）：

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 1 1 1 1 1 0 0 
0 0 0 0 0 1 1 1 0 0
0 0 0 0 1 0 0 1 1 0
0 0 1 1 1 0 1 1 0 0
0 0 1 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

可行解决方案：改进版射线法 #

常规计数奇偶法失效，多是因为未正确处理图形边的厚度、交叉点重复计数问题。改进后的射线法可解决这类场景，核心逻辑如下：

算法步骤 #

1. 边界校验：若目标点(x,y)本身是'1'，或超出矩阵范围，直接返回false；
2. 发射射线：从目标点向固定方向（如水平向右）发射射线，直到矩阵右边界；
3. 交叉计数规则：仅当射线从'0'进入'1'区域时计数+1，避免连续'1'段重复统计；
4. 奇偶判断：交叉次数为奇数则点在内部，偶数则在外部。

代码实现 #

def is_inside(matrix, x, y):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    
    # 边界与自身属性校验
    if x < 0 or x >= rows or y < 0 or y >= cols or matrix[x][y] == '1':
        return False
    
    cross_count = 0
    # 向右遍历当前行的后续元素
    for j in range(y + 1, cols):
        current = matrix[x][j]
        # 仅统计从0到1的首次过渡
        if current == '1' and (j == y + 1 or matrix[x][j-1] == '0'):
            cross_count += 1
    
    return cross_count % 2 == 1

有效性说明 #

• 无论图形规则与否，只要是闭合（或延伸至矩阵边界）的'1'区域，射线法都能准确判断内外；
• 改进的计数规则避免了边厚度带来的重复统计问题，确保每穿过一次边界仅计数一次。

备选方案：种子填充法 #

若射线法的边界判断需更复杂处理，可采用种子填充法：

1. 从目标点出发，用BFS/DFS遍历所有连通的'0'区域；
2. 若遍历过程中到达矩阵边界，说明点在外部；
3. 若遍历完所有连通区域未碰边界，说明点在内部。

代码实现 #

from collections import deque

def is_inside_bfs(matrix, x, y):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    
    if x < 0 or x >= rows or y < 0 or y >= cols or matrix[x][y] == '1':
        return False
    
    visited = set()
    queue = deque([(x, y)])
    visited.add((x, y))
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    while queue:
        cx, cy = queue.popleft()
        # 到达矩阵边界，判定为外部区域
        if cx == 0 or cx == rows-1 or cy == 0 or cy == cols-1:
            return False
        # 遍历四个方向的相邻点
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                if (nx, ny) not in visited and matrix[nx][ny] == '0':
                    visited.add((nx, ny))
                    queue.append((nx, ny))
    # 未到达边界，判定为内部区域
    return True

方案对比 #

• 射线法：时间复杂度O(n)（n为矩阵列数），空间复杂度O(1)，适合快速判断单个点；
• 种子填充法：时间复杂度O(m)（m为连通区域大小），空间复杂度O(m)，适合批量判断同一连通区域的多个点。

内容的提问来源于stack exchange，提问作者Hudson