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.
//dp[i][j][t] == min changes to be made to get to {i,j} in time<=t(It's not just at timestep 't' but also the previous ones). #define INF 1e9+5intcoinOnTheTable(intn,intT,vector<string>board){intr,c;intm=board.size();for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(board[i][j]=='*'){r=i,c=j;break;}}}if(r+c>T)//min required time to get to {r,c}.(Alternate : "return dp[r][c][T]==INF ? -1:dp[r][c][T];" at the end")return-1;intdp[m][n][T+1];memset(dp,INF,sizeof(dp));dp[0][0][0]=0;vector<int>dir={0,1,0,-1,0};for(intt=1;t<=T;t++){for(inti=0;i<m;i++){for(intj=0;j<n;j++){inta,b;if(board[i][j]=='U'){a=i-1,b=j;}elseif(board[i][j]=='D'){a=i+1,b=j;}elseif(board[i][j]=='R'){a=i,b=j+1;}elseif(board[i][j]=='L'){a=i,b=j-1;}for(intp=0;p<4;p++){intx=i+dir[p];inty=j+dir[p+1];if(x<0||y<0||x>=m||y>=n)continue;if(x==a&&y==b){dp[x][y][t]=min(dp[i][j][t-1],dp[x][y][t]);}else{dp[x][y][t]=min(1+dp[i][j][t-1],dp[x][y][t]);}dp[x][y][t]=min(dp[x][y][t],dp[x][y][t-1]);//I forgot to add this step and struggled for an hour. }}}}returndp[r][c][T];}
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 →
Here's my C++ solution.