We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Simple Ruby version. No need to use recursion or backtrack. Just use a simple BFS.
Step by step
- First find the coordinates of starting point and destination.
- Then use BFS with a queue that stores the coordinates of each possible move and the turn count to reach that position.
- In each position, if we have more than 2 possible next moves, then increase turn count by 1
defcount_luck(matrix,k)@matrix=matrix@rows=matrix.length@cols=matrix[0].length# Find the coordinates of starting point and destinationstart_r,start_c,des_r,des_c=0,0,0,0(0..@rows-1).eachdo|r|(0..@cols-1).eachdo|c|start_r,start_c=r,cifmatrix[r][c]=='M'des_r,des_c=r,cifmatrix[r][c]=='*'endend# Use BFS with a queue store the coordinates of each possible move# and the turn count to reach that position@visited={}queue=[[start_r,start_c,0]]untilqueue.empty?cur_r,cur_c,turn=queue.shift@visited[[cur_r,cur_c]]=truereturnturn==k?'Impressed':'Oops!'ifcur_r==des_r&&cur_c==des_c# Generate the next moves from current positionnext_moves=generate_next_moves(cur_r,cur_c)ifnext_moves.length>1turn+=1next_moves.each{|move|queue<<(move<<turn)}elsequeue<<(next_moves[0]<<turn)unlessnext_moves.empty?endendenddefgenerate_next_moves(row,col)res=[]res<<[row-1,col]ifvalid_move?(row-1,col)res<<[row+1,col]ifvalid_move?(row+1,col)res<<[row,col-1]ifvalid_move?(row,col-1)res<<[row,col+1]ifvalid_move?(row,col+1)resenddefvalid_move?(row,col)row>=0&&row<@rows&&col>=0&&col<@cols&&@matrix[row][col]!='X'&&!@visited[[row,col]]end
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Count Luck
You are viewing a single comment's thread. Return to all comments →
Simple Ruby version. No need to use recursion or backtrack. Just use a simple BFS. Step by step - First find the coordinates of starting point and destination. - Then use BFS with a queue that stores the coordinates of each possible move and the turn count to reach that position. - In each position, if we have more than 2 possible next moves, then increase turn count by 1