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

Question

我试图在 Codeforces 中解决一个问题：Maze

从社论中，我了解到我只需要执行 DFS 即可解决此问题。以下是 Editorial 中的确切单词：

Start BFS or DFS from any free cell. As the maze is connected, this search will visit all s free cells. But we can stop the search when it visits s - k free cells. It's obvious that these s - k cells are connected to each other. Remaining k cells can be transformed into the walls.

我的 solution 是：

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 times 仍然无法被接受。

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

注意：这不是作业问题，也不属于任何当前运行比赛的一部分。

Answer 1

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

检查下面的代码(接受):

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("")

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

Codeforces: 377-A Maze, Why is this code not working?

python

algorithm

graph-theory

depth-first-search

graph-traversal