All Tracks>Problem
WinterFell to Kings Landing
★★★★★

0

0 votes
Easy
Problem

Jon Snow wants to travel to Kings Landing From Winterwell to warn them about the White Walkers

He need to visit as much as less no. of castles on the way

So help Jon snow finds the minimum no. of castle he can visit ( as visiting a castle takes a lot of time)

This is a graph problem , so there are (n-2) castles between Winterfell (1st vertex) and Kings Landing (nth vertex) and if graph[i][j] is 1,then there is way from ith castle to jth castle.

1 way will always be guaranteed and no cycle present.

Constraints

1≤n≤103

graph[i][j]= {0,1}

1≤i,j≤n

Input

  • First line represents a integer n denoting number of vertices
  • Each line i of the n subsequent lines contains n integers.

Output

  • For each test case, print a single line containing one integer - minimun no. of intermediate castle visited

No Partial Score in this Question

Sample Input
7
0 1 1 1 0 0 0
0 0 0 0 1 1 1
0 0 0 0 0 1 0
0 0 0 0 0 1 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
Sample Output
1
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

 

  1 2 3 4 5 6 7
1 0 1 1 1 0 0 0
2 0 0 0 0 1 1 1
3 0 0 0 0 0 1 0
4 0 0 0 0 0 1 0
5 0 0 0 0 0 1 0
6 0 0 0 0 0 0 1
7 0 0 0 0 0 0 0

To reach the last vertex from the first one, the shortest way is {1-2-7} traversing only 1 intermediate castle

Some other ways are {1-2-5-6-7} 3 intermediate castle visited , {1-3-6-7} 2 intermediate castle visited  etc

Contributers:
Editor Image

?