0

给定一个矩阵NxM。有 '。' - 您可以访问的单元格和“#” - 您无法访问的单元格。你只能上下左右（不是对角线）。同样给出q请求，在每个单元格中都有需要交换的行和列（如果单元格是“#”，则将其更改为“.”，反之亦然）。对于每个q请求，如果可以从单元格 (sx, sy) 到单元格 (tx, ty)，则打印“是”，如果不可能，则打印“否”。在任何请求下， (sx, sy) 和 (tx, ty) 都不是“#”。

在第一行给出 sx, sy, tx, ty, N, M, q（每一个都是从 1 到 100）。在接下来的 N 行中，给定一个带有 '.' 的矩阵。是空单元格，'#' 是一堵墙。在这 N 行之后，有 q 行有请求。每个都是一对数字，描述要交换的矩阵中的 x 和 y 位置。

在输出中应该有 q 行，如果可以在行的 te 步从起点到达目标点，则每行都为“是”，如果不可能，则为“否”。

示例：（输入）

1 1 2 3 3 3 2
.##
##.
###
1 2
2 2

（输出）

No
Yes

解释

在第一次请求之后，矩阵是

..#
##.
###

在第二次请求之后，矩阵是

..#
#..
###

不幸的是，我没有更多的输入示例。但是，我必须通过网站上的所有未知测试。除了出现时间限制错误的两个测试之外，我在那里解决了所有测试。也许你可以看到如何加快我的代码。顺便说一下，时间限制是0.5秒

我的代码在这里：

sx, sy, tx, ty, n, m, q = map(int, input().split())
arr = [[] for i in range(n)]
for i in range(n):
    line = input()
    arr[i] = [1 if j=='.' else 0 for j in line]
change = [[] for i in range(q)]
for i in range(q):
    change[i] = list(map(int, input().split()))

def is_path(sx, sy, tx, ty, gr):
    visited = []
    path = False

    def dfs(px, py):
        global path
        if (px, py) == (tx, ty):
            return True
        visited.append([px, py])
        for dx in [1, -1]:
            if -1<py+dx<n and gr[px+dx][py] == 1 and [px+dx, py] not in visited:
                if dfs(px+dx, py):
                    return True
        for dy in [1, -1]:
            if -1<py+dy<m and gr[px][py+dy] == 1 and [px, py+dy] not in visited:
                if dfs(px, py+dy):
                    return True
        return False

    return dfs(sx, sy)

for i in range(q):
    arr[change[i][0]-1][change[i][1]-1] += 1
    arr[change[i][0] - 1][change[i][1] - 1] %= 2

    ans = is_path(sx-1, sy-1, tx-1, ty-1, arr)
    if ans: print('Yes')
    else: print('No')
4

1 回答 1

1

主要的算法效率低下是您使用“已访问”集的列表，这导致网格大小的二次最坏情况复杂度。使用set会将其降至线性时间。

除此之外，您还想利用查询之间的一致性。例如，如果一个单元格是可遍历的，那么它不会破坏路径，如果一个单元格是不可遍历的，那么它将永远不会创建路径。您还可以使用不相交的集合结构来观察包含开始和结束单元格的连接组件何时连接。

于 2021-04-05T16:51:18.563 回答