Old Friend

Mah1r_ Unlock The Algorithm, Spr...
Limits 1s, 256 MB

And now it's been a decade since our last adventure together. We promised that we would meet again after a decade, and now the time has come. Captain Jack Sparrow is supposed to be waiting in Tortuga for my arrival, and currently, I am on some islands, reinforcing the necessary supplies for reaching the next island. Now there's a tiny complication: since our last voyage together a decade ago, we've angered the seven warlords of the sea by fooling and conning them. Now I can't face them at any cost since they are still looking for us, and they own islands. So, we can't afford to run into them or their cronies, or we'll end up in Davy Jones' locker. Unfortunately, there's no way to reach Tortuga without crossing some of the islands; we also need supplies to survive. Now I have a map that tells me which island connects with which island. We need a proper plan to solve this issue as quickly as possible. Since we all want to meet Jack quickly, alive, and with less damage to our ship, we need a route that tells us the minimum number of islands we must conquer. There are NN islands numbered from 11 to NN. One of the islands is currently where I am staying, and another island is "Tortuga," where Jack is waiting. We can only go to an island if and only if there's a route to it. It's guaranteed that at least one valid route exists to reach Tortuga.

As the first mate of our ship, can you unfold the path to our voyage quickly?


The first line will be a single integer TT(1T20)(1 \le T \le 20) indicating the number of test cases. The next line contains NN,CC, and XX(1N,C,X100)(1 \le N,C,X \le 100)— indicating NN as the number of islands, CC as the current island, and XX as the island where Jack is. Each of the next NN lines contains NN integers ai,ja_{i,j}(0ai,j1)(0 \le a_{i,j} \le 1)— separated by single spaces. Here ai,ja_{i,j}​ denotes the number in the ithi_{th} row from the top and jthj_{th} column from the left. If the value of ai,ja_{i,j} is 11 that means there is a connection between iiand jj islands, otherwise, 00.


Print the minimum number of islands we have to conquer and the path to reach the Island XXfrom CC. Check out the sample input output for better understanding.


5 1 5
0 1 0 1 0
1 0 0 1 0
0 0 0 0 0
1 1 0 0 1
0 0 0 1 0
Case 1:
1 4 5

There are five islands; currently, we are on the first island and Jack is on the fifth. There's a connection between the islands given in the matrix. The first island has connections to the second and fourth islands. The second island shares routes with the first and fourth islands. Third islands have no route with any island, and so on. The shortest distance between the 1st and 5th islands is through the 4th island.


Login to submit.


75% Solution Ratio
Rakib.4411Earliest, 4M ago
Paul72Fastest, 0.0s
Paul72Lightest, 4.9 MB
Paul72Shortest, 1290B
Toph uses cookies. By continuing you agree to our Cookie Policy.