I tried to solve a question in Codeforces: Maze
From editorial, I understood that I just need to perform a DFS to solve this question. Here are the exact words from 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.
My solution for this is:
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("")
This code is giving wrong answer in Test Case 10 of codeforces but, due to the nature of codeforces website, I do not have access to this Test Case.
I have tried to solve this question more than 20 times still couldn't get it accepted.
I can see other's solutions in the website but why is my code not working?
Note: This is not a homework problem and is not a part of any currently running competition.
When you add an element in a stack i.e s, you should mark that cell with a different symbol so that you can't add that cell again in the stack. Otherwise, it leads to the counting of the same cell as empty space more than a single time. By making these changes in your code, all the test cases were passed.
Check the code below(ACCEPTED):
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("")