https://www.acmicpc.net/problem/16928
INITIAL
I remember solving this on leetcode but I was confused at the time limit of 1s because I thought dfs would take longer than this limit so I tried implementing greedy + bfs. I wanted to skip all next moves if next move coincided with the snake grid and while I have gotten some test cases correct, it is wrong for some.
initial wrong code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n,m=map(int,input().split())
ladders = [list(map(int,input().split())) for _ in range(n)]
snakes = [list(map(int,input().split())) for _ in range(m)]
real = [snake[0] for snake in snakes]
visited = [False for _ in range(101)]
ladders.sort(key= lambda x: (x[0],x[1]))
count =0
def bfs():
queue = deque()
queue.append((1,0))
visited[1]=True
while queue:
cur_pos,cur_cost = queue.popleft()
if cur_pos==100:
return cur_cost
for i in range(6,0,-1):
next_move = cur_pos+i
if 1<=next_move<=100:
if not visited[next_move]:
if next_move not in real:
queue.append((cur_pos+i,cur_cost+1))
visited[next_move]=True
for lad in ladders:
if next_move==lad[0]:
visited[next_move]=True
queue.append((lad[1],cur_cost+1))
val = bfs()
print(val)If we don't visit the snake grids and implement it the greedy way, we are essentially not exploring all possibilities. If snake grid makes us go down to a grid that leads to another ladder that makes us travel in a shorter move, that is the exception i coudldnt think of.
Also use dict for snakes and ladders to access keys and values fast, instead of list
solution
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n,m=map(int,input().split())
ladders={}
snakes={}
for _ in range(n):
a,b = map(int,input().split())
ladders[a]=b
for _ in range(m):
a,b = map(int,input().split())
snakes[a]=b
visited = [False for _ in range(101)]
count =0
def bfs():
queue = deque()
queue.append((1,0))
visited[1]=True
while queue:
cur_pos,cur_cost = queue.popleft()
if cur_pos==100:
return cur_cost
for i in range(6,0,-1):
next_move = cur_pos+i
if 1<=next_move<=100:
if not visited[next_move]:
if next_move in ladders.keys():
next_move = ladders[next_move]
if next_move in snakes.keys():
next_move = snakes[next_move]
if not visited[next_move]:
visited[next_move]=True
queue.append((next_move,cur_cost+1))
val = bfs()
print(val)complexity
o (v +e) so is it n+m time and space?
Your code appears to be implementing a BFS (Breadth-First Search) to navigate a game board with ladders and snakes. The code successfully finds the shortest path from position 1 to position 100. The time complexity is O(V + E), where V is the number of vertices (positions on the board) and E is the number of edges. The space complexity is O(V) for the visited array and O(V) for the queue, so the overall space complexity is O(V).
e is 1 for each vertix so time is just o(v)
