백준 6087번 레이저 통신

Ok i figured out. I was marking the next grid to be visited as ‘’ but when my end condition for bfs is if the current grid is ‘C’. It will thus give None because all the grids will be marked as ‘’, even the ‘C’ before we can meet that condition.

Ok another very important point. I was marking visited as ‘’ but this is a fatal mistake. Think about it. If paths before the answer path has obstructed the future steps of answer path by marking and blocking them as ‘’, then the answer path will NOT be able to traverse further. Thus, in this question we cannot use a regular visited list or mark the grid itself as visited because it will obstruct the future of answer path.

Instead, we should make a check 2d list like
check = [[float('inf')] * W for _ in range(H)]
check[sr][sc] = -1

This check will store the number of mirrors ONLY and will not mark the grid as visited in ANY way.

[fix 30th aug]
but I have seen cases that take visited list so idk how to solve this. I have tried making visited list or marking the grid as visited but all failed and I don't know why it is printing None

wrong:

from collections import defaultdict, deque

rows, cols = map(int, input().split())
graph = []
for i in range(rows):
    graph.append(list(input().strip()))

queue = deque()
mark =[]
for i in range(len(graph)):
    for j in range(len(graph[0])):
        if graph[i][j] == 'C':
            mark.append((i,j))
(sr,sc), (er,ec) = mark
queue.append((sr, sc, 5, 0))

# check = [[float('inf')] * len(graph[0]) for _ in range(len(graph))]
# check[sr][sc] = -1
visited = [[False] * len(graph[0]) for _ in range(len(graph))]

def bfs(queue, graph,er,ec):
    moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while queue:
        cur_x, cur_y, cur_dir, cur_mir = queue.popleft()
        visited[cur_x][cur_y]=True
        if cur_x == er and cur_y ==ec:
            return cur_mir
        for i in range(len(moves)):
            next_x = cur_x + moves[i][0]
            next_y = cur_y + moves[i][1]
            next_dir = i
            if 0 <= next_x < len(graph) and 0 <= next_y < len(graph[0]):
                if graph[next_x][next_y] != '*':
                    if not visited[next_x][next_y]:
                        if cur_dir == next_dir or cur_dir == 5:
                            visited[next_x][next_y] = True
                            queue.append((next_x, next_y, next_dir, cur_mir))
                        else:
                            visited[next_x][next_y] = True
                            queue.append((next_x, next_y, next_dir, cur_mir + 1))


ans = bfs(queue, graph,er,ec)
print(ans)