https://www.codechef.com/viewsolution/29175238
I used dfs as well, what is wrong with this approach?
https://www.codechef.com/viewsolution/29175238
I used dfs as well, what is wrong with this approach?
vi Dist(N, -1); Dist[0] = 0;
queue<int> Q; Q.push(0);
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(auto i : Adj[u]){
if(Dist[i] != -1) continue;
Dist[i] = Dist[u] + 1;
Q.push(i);
}
}
cout << Dist[N - 1] << endl;
can anyone explain me how this part works?
this is standard bfs with single source shortest path in unweighted graphs
can someone plxx tell me why my code is giving TLE for the 2nd subtask. I use DP and queue approach(not in a perfect DFS/BFS manner).
Try without pair in queue i also got same TLE
Ok I got AC the issue was that I was not doing visited=true while adding in queue so multiple similar elements were getting pushed in queue that is leading to TLE
Can Anybody Please Tell me why this code is showing wrong answer for POPTUNNL
I included all the necessary comments
Thanks in advance
#include <bits/stdc++.h>
using namespace std;
int p=INT_MAX;
void check(map<int,string>m,int n,int k,int first,int c,map<int,int>visited)
{
//cout<<“first=”<<first<<endl;
if (first==n)
{
//cout<<“c=”<<c<<endl;
p=min(p,c); //taking the minimum count to reach at end vertex
return ;
}
for(int i=max(first-k,1);i<=min(first+k,n);i++)
{
//cout<<“i=”<<i<<endl;
if (i!=first&&visited[i]==0&&m[first][i]==‘1’) // checking the condition
{
visited[i]=1; //marking as this vertex is visited
return check(m,n,k,i,c+1,visited); // exploration of new vertex
visited[i]=0; // unmarking the visited vertex
}
}
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
map<int,string>m;
string s;
for (int i=1;i<=n;i++)
{
cin>>s;
s=“0”+s; // here to make index start with 1 i add 0
m[i]=s;
}
map<int,int>visited; // for visited vertex
visited[1]=1;
check(m,n,k,1,0,visited);
if (p==INT_MAX)
cout<<-1<<endl;
else
cout<<p<<endl;
p=INT_MAX;
}
}
here we are visiting all the adjacent nodes to current node , i.e Adj[u] , where u is current node
and the dist to child node is dist of current node + 1, i.e Dist[i] = Dist[u] + 1; and push ( i ) in queue ,(i is the child node).
Thank you for your achar. oops vichaar
Can anyone please provide test cases for this question , examples are showing correct results but subtasks are giving WA?
I used DIJKSTRA algorithm on the adjacency matrix, got AC partially ,remaining subtasks gives WA, what is wrong with DIJKSTRA approach my solution by dijkstraas compared with BFS approach
Good point…I ll check my solution again
You can simply do it using Single Source Shortest Pah.It’s nicely explained here : Under The Tunnels | CodeChef Jan Lunchtime Solution | Algorithm and Code Explanation by alGOds!! - YouTube
It’s nicely explained here : Under The Tunnels | CodeChef Jan Lunchtime Solution | Algorithm and Code Explanation by alGOds!! - YouTube
can’t this be solved using dp ?
if then someone has solved it plz reply
I used recursion to solve the question and got AC in 4 tasks out of 5. Can someone tell me what’s wrong in my code?
https://www.codechef.com/viewsolution/31739270
Yes, I have solved it partially using recursion, but it only passes the first subtask and for the second one it gives TLE, however I have a DP solution also which passes with AC.
The recursion solution as you are asking is here.
Link- CodeChef: Practical coding for everyone