时间戳

首页 > 解决方案 > Codeforces：377-A Maze，为什么这段代码不起作用？

python - Codeforces：377-A Maze，为什么这段代码不起作用？

问题描述

我试图解决 Codeforces 中的一个问题：迷宫

从社论中，我了解到我只需要执行 DFS 来解决这个问题。以下是社论的原话：

从任何空闲单元启动 BFS 或 DFS。随着迷宫的连接，此搜索将访问所有 s 个空闲单元。但是我们可以在它访问 s - k 个空闲单元格时停止搜索。很明显，这些 s - k 细胞是相互连接的。剩余的 k 个细胞可以转化为壁。

我的解决方案是：

n, m, k = map(int, input().split())
arr = [list(input()) for _ in range(n)]  # The maze

if k == 0:  # if no wall needed, print maze as it is and exit
    for row in arr:
        for element in row:
            print(element, end="")
        print("")
    exit(0)

x, y = -1, -1  # indices to start DFS with, x and y can point to any cell which is '.' (empty)
to_visit = -k  # the number of connected components of graph we need to visit(remaining '.' cells will be marked as 'X')
for i in range(n):
    for j in range(m):
        if arr[i][j] == '.':
            to_visit += 1
            x = i
            y = j


s = [(x, y)]  # a stack for performing DFS
while to_visit > 0 and len(s) > 0:
    i, j = s.pop()
    arr[i][j] = '?'  # make it anything other than '.', '#' and 'X', to mark it visited.
    #                  so we can later remaining '.' to 'X' and change '?' to '.'
    to_visit -= 1
    # top
    if i > 0 and arr[i - 1][j] == '.':
        s.append((i - 1, j))
    # bottom
    if i < n - 1 and arr[i + 1][j] == '.':
        s.append((i + 1, j))
    # left
    if j > 0 and arr[i][j - 1] == '.':
        s.append((i, j - 1))
    # right
    if j < m - 1 and arr[i][j + 1] == '.':
        s.append((i, j + 1))


for row in arr:
    for element in row:
        if element == '?':
            print('.', end="")
        elif element == '.':
            print('X', end="")
        else:
            print(element, end="")
    print("")

此代码在 codeforces 的测试用例 10 中给出了错误的答案，但由于 codeforces 网站的性质，我无权访问此测试用例。

我已经尝试解决这个问题超过20 次，但仍然无法被接受。

我可以在网站上看到其他人的解决方案，但为什么我的代码不起作用？

注意：这不是一个家庭作业问题，也不是任何当前正在运行的比赛的一部分。

标签： pythonalgorithmgraph-theorydepth-first-searchgraph-traversal

解决方案

当你在栈中添加一个元素时，你应该用不同的符号标记那个单元格，这样你就不能在栈中再次添加那个单元格。否则，它会导致多次将同一单元格计算为空白空间。通过在代码中进行这些更改，所有测试用例都通过了。

检查下面的代码（接受）：

n, m, k = map(int, input().split())
arr = [list(input()) for _ in range(n)]  # The maze

if k == 0:  # if no wall needed, print maze as it is and exit
    for row in arr:
        for element in row:
            print(element, end="")
        print("")
    exit(0)

x, y = -1, -1  # indices to start DFS with, x and y can point to any cell which is '.' (empty)
to_visit = -k  # the number of connected components of graph we need to visit(remaining '.' cells will be marked as 'X')
for i in range(n):
    for j in range(m):
        if arr[i][j] == '.':
            to_visit += 1
            x = i
            y = j


s = [(x, y)]  # a stack for performing DFS
while to_visit > 0 and len(s) > 0:
    i, j = s.pop()
    arr[i][j] = '?'  # make it anything other than '.', '#' and 'X', to mark it visited.
    #                  so we can later remaining '.' to 'X' and change '?' to '.'
    to_visit -= 1
    # top
    if i > 0 and arr[i - 1][j] == '.':
        s.append((i - 1, j))
        arr[i-1][j] = '@'
    # bottom
    if i < n - 1 and arr[i + 1][j] == '.':
        s.append((i + 1, j))
        arr[i+1][j] = '@'
    # left
    if j > 0 and arr[i][j - 1] == '.':
        s.append((i, j - 1))
        arr[i][j-1] = '@'
    # right
    if j < m - 1 and arr[i][j + 1] == '.':
        s.append((i, j + 1))
        arr[i][j+1] = '@'


for row in arr:
    for element in row:
        if element == '?':
            print('.', end="")
        elif element == '.' or element == '@':
            print('X', end="")
        else:
            print(element, end="")
    print("")

推荐阅读