manni991 ron won't be impressed very much, once he get to know hermione used backtracking
tcharding Two thumbs up
rajeev11430 True that. Stack Overflows.
zainul118 solved the maze using backtracking but how to count the guesses??
amsborse did it by brute force if else if else :P
saketk21 Everytime you push a branching node on the final path on the stack, increment the count. At the end, if the count equals K, then Ron impresses Hermione.
snaran Should we use a stack or a queue? I think either would work, but not sure which would be faster. In my solution, the thing I pushed onto the queue was the node (x, y position) plus the, number of intersection encountered to have reached that point.
In the case that there are multiple routes to the final point, it might be more complicated.
saketk21 Either works. Just that the question suggests backtracking and so I used a stack :)
rwan7727 Global vars are char **a, int numCrossJunctions, bool found
Function move with r,c,n,m as inputs:
if (found) return; int numPath=0; //try up if ((r-1)>=0) { // check for boundary first if (a[r-1][c]=='.') { a[r][c]='X'; numPath++; move(r-1,c,n,m); } else if (a[r-1][c]=='*') { numPath++; found=true; } } //try down if ((r+1)<n) { // check for boundary first if (a[r+1][c]=='.') { a[r][c]='X'; numPath++; move(r+1,c,n,m); } else if (a[r+1][c]=='*') { numPath++; found=true; } } //try left if ((c-1)>=0) { // check for boundary first if (a[r][c-1]=='.') { a[r][c]='X'; numPath++; move(r,c-1,n,m); } else if (a[r][c-1]=='*') { numPath++; found=true; } } //try right if ((c+1)<m) { // check for boundary first if (a[r][c+1]=='.') { a[r][c]='X'; numPath++; move(r,c+1,n,m); } else if (a[r][c+1]=='*') { numPath++; found=true; } } if (found && (numPath>1)) numCrossJunctions++;In main:
int t; cin >> t; for (int test=0;test<t;test++) { int n,m; cin >> n >> m; // allocate memory for grid a=(char **)malloc(sizeof(char *)*n); a[0]=(char *)malloc(sizeof(char)*n*m); for(int i=0;i<n;i++) a[i]=(*a+m*i); // input grid & k int startrow,startcol; for (int r=0;r<n;r++) for (int c=0;c<m;c++) { cin >> a[r][c]; if (a[r][c]=='M') { // found M position startrow=r; startcol=c; } } int k; cin >> k; // process found=false; numCrossJunctions=0; move(startrow,startcol,n,m); // start from M // Determine output if (numCrossJunctions==k) cout << "Impressed" << endl; else cout << "Oops!" << endl; // free grid free(a[0]); free(a); }snaran But if you backtrack, you have to revert numCrossJunctions to what it was? My solution was to have a Queue of paths (which is a point plus the number of interesections to reach this point), and if there is more than 1 direction, then add both new points to the queue.
Do you have to keep track of going back to the point you came from? So I also marked a point as visited, but not 100% sure if this is necessary.
snaran She didn't use backtracking. We used backtracking, queues with multiple paths, etc to prove her right, but the wand was magic.
m_a_r_c_e_li_n_o Piggybacking on a few complaints made here, I think that labeling this challenge as "easy" is a bit misleading. The amount of rational required to solve it seems fairly close to another challenge in this section called "Connected Cell in a Grid" and that one is labeled as "Moderate". Regardless, easy or not, this challenge is a great quest and the sum of points awarded is reasonable.
For those struggling, try a recursive "Depth First Search" approach where you bubble up information about the amount of forks in the path leading up to the exit point, denoted as a * in the grid. There will only be one path to the exit point, all others will terminate in a dead end and you should discard all information related to those useless paths.
Here's an informal test case to help you catch some edge cases:
5
3 6
*.M...
.X.X.X
XXX...
1
3 6
*..M..
.X.X.X
XXX...
2
3 6
*M....
.X.X.X
XXX...
1
3 6
*....M
.X.X.X
XXX...
2
3 6
*.....
.X.X.X
XXX.M.
3All five should return "Impressed".
arkalyk This test saved me!
piniMeister Cheers mate!
shshnk28 These simple test cases saved my day. Thanks!
ankit711m Bazinga!!
AnuragSinha Thanks, very helpful!
xuhuanze Thanks. Corner cases are much more helpful than those large tests.
MrAsimov thank you.
I_am_Nobody Can u please point out the error or make necessary corrections?
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long int #define mod 10000007 #define rep(a,b,c) for(int i=a;i<=b;i+=c) #define repi(a,b,c) for(int i=a;i>=b;i-=c) #define lb lower_bound #define ub upper_bound #define pushb push_back #define popb pop_back using namespace std; char f[101][101]; bool v[101][101]; int k,Count=0; void dfs(int n,int m,int i,int j) { v[i][j]=1; if(f[i][j+1]=='*') return ; else if(f[i][j-1]=='*') return ; else if(f[i-1][j]=='*') return ; else if(f[i+1][j]=='*') return ; if(!v[i][j-1]&&!v[i+1][j]&&f[i][j-1]=='.'&&f[i+1][j]=='.') Count++; else if(!v[i][j-1]&&!v[i-1][j]&&f[i][j-1]=='.'&&f[i-1][j]=='.') Count++; else if(!v[i][j-1]&&!v[i][j+1]&&f[i][j-1]=='.'&&f[i][j+1]=='.') Count++; else if(!v[i+1][j]&&!v[i][j+1]&&f[i+1][j]=='.'&&f[i][j+1]=='.') Count++; else if(!v[i+1][j]&&!v[i-1][j]&&f[i+1][j]=='.'&&f[i-1][j]=='.') Count++; else if(!v[i][j+1]&&!v[i-1][j]&&f[i][j+1]=='.'&&f[i-1][j]=='.') Count++; if(!v[i+1][j]&&f[i+1][j]=='.') dfs(n,m,i+1,j); if(!v[i-1][j]&&f[i-1][j]=='.') dfs(n,m,i-1,j); if(!v[i][j-1]&&f[i][j-1]=='.') dfs(n,m,i,j-1); if(!v[i][j+1]&&f[i][j+1]=='.') dfs(n,m,i,j+1); } int main() { int t; cin>>t; while(t--) { int n,m,i,j; cin>>n>>m; Count=0; memset(f,'X',sizeof(f)); memset(v,false,sizeof(v)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { cin>>f[i][j]; } cin>>k; int I,J; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(f[i][j]=='M') { I=i; J=j; if(!v[i][j]) { dfs(n,m,i,j); } } } if(Count==k) cout<<"Impressed"<<endl; else cout<<"Oops!"<<endl; } return 0; }
VasilyM What obfuscator did you use?
schen175 Make sure your not including the dest node when your counting the # of nodes with more than 1 fork
RahulWadekar Thanks. These test cases were very helpful.
john_canessa Harder than expected. Love it. Keep them coming !!!
nirvik1993 these were extremely helpful !
abhinitsati [deleted]sidajwalia this set helped me.
MrMafia I think they have changed the test cases now because we should not count the wand swings after reaching the destination.
AKSaigyouji This problem is more straightforward than I think most (even the problem setter) realize.
Do a simple BFS or DFS to find the unique path from the start to the exit. Then, for each point in the path excluding the start and finish, count the number of neighbors. If the number of neighbors is more than 2, that's a fork, and you can add 1 to your running total. Finally, add another 1 if the start has more than 1 neighbor.
No backtracking or recursion. Just a BFS to find a path, then a linear pass over the path to count forks.
tombombadillo Yesss.
I did the same, completed within an hour, came to the comments to look for more elegant solutions, only to find everyone talking about complicated recursion, backtracking algorithms and complaining about the dificulty hahahah.
Matt_Scandale This challenge should be worth 100 points (not 45) and it should be classified as "Advanced" (not "Easy"). It took me 10 hours and nearly 200 lines of code. And I still didn't pass all the test cases. And it should be named something like "Navigate the Maze" which would be more descriptive.
AllisonP Thank you for the feedback. The challenge difficulty has been raised to Moderate, and the point value has been raised to 50. Due to the relatively high rate of success (80%) for this challenge, it would not qualify as an Advanced challenge.
Arun_DMan I think success rate should not be a measure of difficulty, or I can say that difficulty of a question should not depend on its success rate.
shreyansh2495 use backtrack its easy buddy
ravioactive My code fails for the same particular input inside more than one test case, which I managed to identify after unlocking the test case. It is the last input in test case 2, and last but 3rd input in test case 6. I do not want to spoil it for other participants, so I am reluctant to give the input here, but the admins should know which one I'm referring. The given value of K in the test case is 294, while my code is returning 479. It works for all the other cases, except this, so I am not sure what am I getting wrong.
My submission is the following: https://www.hackerrank.com/challenges/count-luck/submissions/code/11456984
Can anyone help me out please?
EDIT: got it, I'm counting all the branches, instead of the only path which leads to the exit. That is a good test case.
ayushchatur i am getting same Wrong amswer with my submission can u explain what is wrong in the logic ... briefly
Titas_Nandi I am stuck at the same place! Can you help me figure it out?
ayushchatur check the boundary conditions thoroughly ... and the logic ... there is a glitch in the first logic that hits the mind ...download input test cases and run thoroughly .. u can also look into my solution ..but i wont recommend that ... it is a very good problem and i advise you to not to give up .!! and try even harder and better
ashishsahu2008 [deleted]
ignorantCity Not too bad once you read up on backtracking - was able to come up with a relatively short recursion to solve the maze then use the solution as an input to check the 'chance' condition for the final output.
Found this to be quite helpful: https://www.cs.bu.edu/teaching/alg/maze/
dgpskundu thanks for the link:)
iamnvd How does this question even qualify as easy. Or am I missing something. Please Help.
prabodhprakashAsked to answer I have not solved the question, but from what I undestood - she always go on the right path and you have to tell the number of points where she had multiple choices to chose a path from.
For e.g. If the path is like A-->B and B-->C and B-->D
and A-->B-->C is the right path, then at B she had two choices and she would use her wand.
One option could be using shortest path algorithm to find out the shortest (which is also the only path) possible path and in that path you have to find number of points where there were multiple choices of path selection.
I would also say that a simple DFS will also solve the question (given there is only one unique path - which makes it tree and not a graph).
AllisonP The challenge difficulty is now upgraded to Moderate.
nikweber Yes - this was a fun problem! Thank you!
lonewolff wasnt too tough but took a lot of time than expected... a little trick.. instead of checking for boundary conditions or using exception handling just surround the matrix by a "X" outer block. all the best to others.
Sort 107 Discussions, By:
Please Login in order to post a comment