arnie41178
BAN USERFollowing is the logic:
We take a bottom-up approach where from 2 to Total_steps we keep on solving problem using values computed for sub-problems. We have to keep auxiliary data structure for storing the paths computed for each value of steps.
typedef list<num> AllowedStepList; # List of allowed steps
typedef list<num> Path; # Step list constituting the path
typedef list<Path> PathList; # List of paths for a step-value
typedef vector<PathList> PathListVector; # PathList for each step value
AllowedStepList allowedStepList; // Assume allowedStepList contains all the steps provided
int STEP_COUNT; # Total steps to be convered
PathListVector pathListVec(STEP_COUNT);
// Initialize path list for step-0 path
Path path0;
PathList pathList0;
pathList0.push_back(path0);
pathListVec[0].push_back(pathList0);
for (int i = 1; i < STEP_COUNT; i++)
{
BOOST_FOR_EACH(AllowedStepList::value_type& step, allowedStepList)
{
// Try out each step to get paths for covering total i steps.
if (step > i)
{
continue;
}
PathList& stepPathList = pathListVec[i - s]; // The preceding pathlist to add i as the last steps
BOOST_FOR_EACH(PathList::value_type& path, stepPathList)
{
// i could the next step only if the last step was {i or (i - 1) or (i + 1))
if ((path.back() == s) || (path.back() == (s - 1)) || (path.back() == (s + 1)))
{
Path newPath(path);
newPath.push_back(step);
pathListVec[i].push_back(newPath);
}
}
}
}
pathListVec[STEP_COUNT - 1] contains all the possible paths
pathListVec[STEP_COUNT - 1].front() is the most efficient path
Assuming the problem is for a 2-D (r*c) array, here is my solution.
We maintain a min-heap which initially contains the first element of each column (total c elements). We also maintain the row,column index of each element along with the element.
struct arrayelem
{
int elem;
int rowIndex;
int colIndex;
};
// Initially the min-heal contains the first element of each column.
while (--k > 0)
{
topelem = min-heap->pop();
// The element int the next row in the same column as topelem is pushed in the heap
newRowIndex = ++topelem->rowIndex;
newColIndex = topelem->colIndex;
newelem = new arrayelem(array[newRowIndex ][newColIndex],
newRowIndex, newColIndex);
min-heap->push(newelem);
}
return newelem->elem;
Assuming the problem is for a 2-D (r*c) array, here is my solution.
We maintain a min-heap which initially contains the first element of each column (total c elements). We also maintain the row,column index of each element along with the element.
struct arrayelem
{
int elem;
int rowIndex;
int colIndex;
};
// Initially the min-heal contains the first element of each column.
while (--k > 0)
{
topelem = min-heap->pop();
// The element int the next row in the same column as topelem is pushed in the heap
newRowIndex = ++topelem->rowIndex;
newColIndex = topelem->colIndex;
newelem = new arrayelem(array[newRowIndex ][newColIndex],
newRowIndex, newColIndex);
min-heap->push(newelem);
}
return newelem->elem;
- arnie41178 May 16, 2012