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.
Another approach is to find the minimum number of steps required to reach all reachable cells using a certain number of operations.
Let dp[i, j, c] = minimum number of steps to reach cell (i, j) using c operations.
This can be done using BFS, starting at (i, j) = (0, 0) with c = 0. Explore every reachable node from (0, 0) while using 0 operation. While exploring you will also find cells that require c + 1 (= 1 in this iteration). Put those aside in a separate queue. Then re-do this process for all the nodes in that seperate queue.
publicstaticintCoinOnTheTable(intn,intm,intk,(intI,intJ)dest,char[,]board){if(k<dest.I+dest.J){return-1;}varmc=dest.I+dest.J;vardp=newint[n,m,mc+2];for(vari=0;i<n;++i){for(varj=0;j<m;++j){for(varc=0;c<mc+2;++c){dp[i,j,c]=int.MaxValue;}}}dp[0,0,0]=0;varcurQueue=newQueue<(intI,intJ)>();varnextQueue=newQueue<(intI,intJ)>();curQueue.Enqueue((0,0));varmoves=new[]{(-1,0,'U'),(0,1,'R'),(1,0,'D'),(0,-1,'L')};for(varc=0;c<=mc;++c){while(curQueue.TryDequeue(outvarcoords)){vari=coords.I;varj=coords.J;foreach(var(di,dj,dir)inmoves){if(i+di<0||i+di>=n||j+dj<0||j+dj>=m){continue;// out of bounds}varc2=board[i,j]==dir?0:1;if(dp[i+di,j+dj,Math.Max(0,c-1)]<=dp[i,j,c]+1||dp[i+di,j+dj,c]<=dp[i,j,c]+1||dp[i+di,j+dj,c+c2]<=dp[i,j,c]+1){continue;// we've found better already}dp[i+di,j+dj,c+c2]=dp[i,j,c]+1;(c2==0?curQueue:nextQueue).Enqueue((i+di,j+dj));}}(curQueue,nextQueue)=(nextQueue,curQueue);}for(varc=0;c<=mc;++c){if(dp[dest.I,dest.J,c]<=k){returnc;}}thrownewException();// unreachable}
The only trick here is that the dp array is partially kept up to date. For example, dp[0, 0, 0] = 0, but dp[0, 0, >0] = inf. This doesn't affect anything because dp[, , c] will only ever be compared with dp[, , c + { -1, 0, 1 }]. It will never incorrectly interpret a hole left by the partial update as a potential better solution, because it won't look at such holes.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Coin on the Table
You are viewing a single comment's thread. Return to all comments →
Another approach is to find the minimum number of steps required to reach all reachable cells using a certain number of operations.
Let dp[i, j, c] = minimum number of steps to reach cell (i, j) using c operations.
This can be done using BFS, starting at (i, j) = (0, 0) with c = 0. Explore every reachable node from (0, 0) while using 0 operation. While exploring you will also find cells that require c + 1 (= 1 in this iteration). Put those aside in a separate queue. Then re-do this process for all the nodes in that seperate queue.
The only trick here is that the dp array is partially kept up to date. For example, dp[0, 0, 0] = 0, but dp[0, 0, >0] = inf. This doesn't affect anything because dp[, , c] will only ever be compared with dp[, , c + { -1, 0, 1 }]. It will never incorrectly interpret a hole left by the partial update as a potential better solution, because it won't look at such holes.