Python Code for WebPages (TCS Codevita) | PrepInsta
WebPages
TCS CodeVita is a coding competition organized by TCS every year, in search of world’s best coder. This is a global level coding competition in which coders from all around the world compete for the title of World’s Best Coder. WebPages is one of the sample problem of this year TCS CodeVita season 11 competition.
Question -: Consider a set of web pages, numbered from 1 to N. Each web page has links to one or more web pages. Clicking on a link in a page, takes one to the other web page. You are provided numbers of two web pages viz, starting web page and end web page. Your task is to find the minimum number of clicks required to reach the end page from the start page. If end page cannot be reached from start page, print -1 as the output. For better understanding refer Examples section.
Constraints
0 < N <= 100
0 < L < 10
Input
First line contains an integer N denoting number of web pages.
Next N lines contain L space separated integers depicting linked webpage number(s) from that webpage
Output
Print the minimum number of clicks required to open the end page from start page. If not possible, print -1 as output.
Time Limit (secs)
1
Example 1
Input
5
2 4
1
1 5
2 3
5
2 3
Output
3
Explanation:
First line conveys that there is total 5 pages.
Second line conveys that there are links from page 1 to pages 2 and 4.
Third line conveys that there is a link from page 2 to page 1.
Fourth line conveys that there are links from page 3 to pages 1 and 5.
Fifth line conveys that there are links from page 4 to pages 2 and 3.
Sixth line conveys that there is a links from page 5 to page 5 itself.
Seventh line conveys that starting page is 2 and ending page is 3
From page 2, we can open only page 1. From page 1, we can open page 4. From page 4, we can open page 3. So, minimum 3 clicks are required, and this is the output.
Example 2
Input
3
2
1
1
2 3
Output
-1
Explanation:
First line conveys that there is total 3 pages.
Second line conveys that there are links from page 1 to page 2.
Third line conveys that there is a link from page 2 to page 1.
Fourth line conveys that there are links from page 3 to page 1.
Since there is no way to reach from page 2 to page 3, print -1 as output.
from collections import deque
def find_min_clicks(N, pages, start, end):
visited = [False] * (N + 1)
queue = deque([(start, 0)])
while queue:
current_page, clicks = queue.popleft()
visited[current_page] = True
if current_page == end:
return clicks
for linked_page in pages[current_page]:
if not visited[linked_page]:
queue.append((linked_page, clicks + 1))
return -1
N = int(input())
pages = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
pages[i] = list(map(int, input().split()))
start, end = map(int, input().split())
result = find_min_clicks(N, pages, start, end)
print(result, end='')
Login/Signup to comment