Uchman21
BAN USERNote: Just wrote this up. Please check, I didn't run this code to confirm if its bug-free.
Assuming all the costs are non-negative, We can use Dynamic Programming method. There are different ways to parse the string to a 2D array. we can get the numbers and insert them row by row into a 2D array.
Assuming we have done that and parsed them into a 2D vector array Paths, then
class MinimumCost{
Public:
unsigned int getMin(std::vector<vector<int> > &Paths, int i, int j){
int up = INT_MAX, left = INT_MAX, Diag = INT_MAX
if(i - 1 >= 0){
up = Paths[i-1][j];
if(j - 1) >= 0)Diag = Paths[i-1][j-1];
}
if (j - 1) >= 0){
left = Paths[i][j-1];
}
unsigned int Min = std::min(left,min(up, Diag));
if( Min == INT_MAX) return 0;
return Min;
}
std::string BackTrack(std::vector<vector<int> > &PathCosts, int i, int j){
std::string Path = “”;
while(i >= 0 || j >=0){
int Min = getMin(PathCosts,i,j);
if ( i -1 >= 0 && Min == PathCosts[i-1][j]){
i = i - 1;
Path = “R” + Path;
}else if (i -1 >= 0 && j -1 >= 0 && Min == PathCosts[i-1][j-1]{
i = i - 1;
j = j - 1;
Path = “D” + Path;
}else {
j = j -1;
Path = “B” + Path;
}
}
return Path;
}
std::string getShortestPath(std::vector<vector<int> > Paths){
std::vector<vector<int> > PathCosts;
int len = Paths.size();
std::string Path = “”;
PathCosts.resize(len);
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
PathCost[i].resize(len);
PathCost[i][j] = Paths[i][j] + getMin(Paths,i,j);
}
}
return std::to_string(PathCost[len - 1][len - 1]) + “,” + BackTrack(PathCost, len - 1, len - 1);
}
};
#include <ctime>
class DropBoxHitRecord{
public:
static int ID;
static map<time_t, unsigned int> Hit;
void recordHit(){
ID++;
Hit.insert(std::make_pair(time(0), ID));
}
long getCount(){
long count = 0;
std::map<time_t, unsigned int>::iterator It;
It = Hit.lower_bound(time(0)- 300);
for (; It != Hit.end(); ++It){
count++;
}
return count;
}
};
Note: Just wrote this up. Please check, I didn't run this code to confirm if its bug-free.
Assuming all the costs are non-negative, We can use Dynamic Programming method. There are different ways to parse the string to a 2D array. we can get the numbers and insert them row by row into a 2D array.
Assuming we have done that and parsed them into a 2D vector array Paths, then
- Uchman21 April 27, 2016