Expensive Travel
//============================================================================
// Name : multiFactorial.cpp
// Author : nick
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
/****************************************************************************************************
Problem Statement
You are lost in a strange land and have to return to the base camp as
soon as possible. The land is modeled as a rectangular plane divided
into square cells, and each cell can be of one of 9 different types,
numbered from 1 to 9. The cost of a cell of type k is exactly 1/k.
To get to the base camp, you can move from each cell to any of its
orthogonally adjacent cells (up, down, left or right) instantaneously.
The only limitation for the speed of your movements is the
cost-per-minute. Time will be divided into one minute intervals, i.e.,
there is an interval starting at time 0 and ending at time 1, another
interval from time 1 to time 2, etc. During each interval of time, the
sum of the costs of all the cells you occupy must not exceed 1. If you
make an instantaneous move at the exact boundary between two intervals
of time, the cells you move between during that move will count toward
both intervals' total costs. This means you can never step into or out
of a cell of type 1 because any other cell you occupy will always
exceed the maximum cost per minute.
You will be given m, a vector <string> describing the land, where
the jth character of the ith element represents the type of the cell at
row i, column j (both 1-based). You will also be given startRow,
startCol, endRow and endCol, the 1-based indices of the row and column
of your starting point and destination, respectively. Return the
minimum number of minutes that are needed to get from (startRow,
startCol) to (endRow, endCol) following the constraints above. If it's
impossible to do so, return -1.
Definition
Class:
ExpensiveTravel
Method:
minTime
Parameters:
vector <string>, int, int, int, int
Returns:
int
Method signature:
int minTime(vector <string> m, int startRow, int startCol, int endRow, int endCol)
(be sure your method is public)
Constraints
-
m will contain between 1 and 50 elements, inclusive.
-
Each element of m will contain exactly N characters, where N is an integer between 1 and 50, inclusive.
-
Each character of each element of m will be a digit between '1' and '9', inclusive.
-
startRow and endRow will each be between 1 and the number of elements in m, inclusive.
-
startCol and endCol will each be between 1 and the number of characters in the first element of m, inclusive.
-
Either startCol will be different from endCol or startRow will be different from endRow.
Examples
0)
{"22334"}
1
1
1
5
Returns: 3
During the first minute, you can move 1 cell to the right. The two
cells that you occupy during that minute are both of type 2, so the
cost is 1/2+1/2=1. In the second minute, you can move 1 more cell to
the right. You cannot go any further because 1/2+1/3+1/3 > 1. During
the third minute, you can reach your destination by moving 2 cells to
the right for a cost of 1/3+1/3+1/4 < 1.
1)
{"55",
"52",
"55"}
1
2
3
2
Returns: 1
You can step on all 5 5's during the same interval, so you can get there in just 1 minute.
2)
{"251",
"212",
"122"}
1
1
3
3
Returns: -1
Since it's impossible to step into a cell of type 1, there is no way to get to your destination.
3)
{"452232",
"287979",
"219872",
"928234",
"767676"}
1
6
3
1
Returns: 3
4)
{"11"}
1
1
1
2
Returns: -1
5)
{"123456789987654321"}
1
2
1
16
Returns: 5
This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
***************************************************************************************************************/
#include <string>
#include <vector>
#include <iostream>
using namespace std;
struct Context
{
int minute;
double reachingCost;
double cost;
};
typedef vector<Context> ContextVector;
typedef vector<ContextVector> ContextMatrix;
class ExpensiveTravel
{
private:
size_t row, col;
void initContextMatrix(ContextMatrix& ctxMatrix, const vector<string>& m)
{
for (size_t r = 0; r < row; r ++)
{
ContextVector aRow;
for (size_t c = 0; c < col; c ++)
{
Context ctx;
ctx.minute=0;
ctx.reachingCost=1.0;
ctx.cost= 1.0 / (double)(m[r][c] - '0');
aRow.push_back(ctx);
}
ctxMatrix.push_back(aRow);
}
}
bool canMove(size_t r, size_t c)
{
return r >= 1 && r <= row && c >=1 && c <= col;
}
bool testMove(ContextMatrix& ctxMatrix, size_t curRow, size_t curCol, size_t nxtRow, size_t nxtCol)
{
if (!canMove(nxtRow, nxtCol))
{
return false;
}
Context& curCtx = ctxMatrix[curRow-1][curCol-1];
Context& nxtCtx = ctxMatrix[nxtRow-1][nxtCol-1];
// if next minute is 0, create it
if (nxtCtx.minute == 0)
{
// if we can reach it within this minute
if (curCtx.reachingCost + nxtCtx.cost < 1.0)
{
// update the cost
nxtCtx.minute=curCtx.minute;
nxtCtx.reachingCost = curCtx.reachingCost +
nxtCtx.cost;
}
else
{
// but we will stuck if next has cost of 1
if (nxtCtx.cost == 1.0)
{
return false;
}
// then we have to start it in next minute;
nxtCtx.minute = curCtx.minute + 1;
nxtCtx.reachingCost = nxtCtx.cost;
}
return true;
}
else
{
// or if it is an old-reachable cell but we can do better
if
(nxtCtx.minute == curCtx.minute && curCtx.reachingCost +
nxtCtx.cost < nxtCtx.reachingCost)
{
nxtCtx.reachingCost = curCtx.reachingCost +
nxtCtx.cost;
return true;
}
// can reach
it within this minute // or within same minute, but lower cost
if (nxtCtx.minute > curCtx.minute)
{
// first case, we can reach it within same minute
if ((curCtx.reachingCost + nxtCtx.cost) < 1.0)
{
nxtCtx.minute = curCtx.minute;
nxtCtx.reachingCost =
curCtx.reachingCost + nxtCtx.cost;
return true;
}
// we can always reach it in next minute, because it
is not "trap"(since somebody already reach it before
// case one: it should be reachable next minute
if ((nxtCtx.minute > curCtx.minute + 1)
// case two:
it is next minute, but it should be a brand new start
||((nxtCtx.minute == curCtx.minute + 1) && nxtCtx.reachingCost
> nxtCtx.cost))
{
nxtCtx.minute = curCtx.minute + 1;
nxtCtx.reachingCost = nxtCtx.cost;
return true;
}
}
}
return false;
}
void expandCell(ContextMatrix& ctxMatrix, size_t curRow, size_t curCol)
{
//debug
// sanity test
if (ctxMatrix[curRow-1][curCol-1].cost == 1.0)
{
return;
}
size_t nxtRow, nxtCol;
// move up
nxtRow = curRow -1;
nxtCol = curCol;
if (testMove(ctxMatrix, curRow, curCol, nxtRow, nxtCol))
{
// we have new updates, so expand more
expandCell(ctxMatrix, nxtRow, nxtCol);
}
// move down
nxtRow = curRow + 1;
nxtCol = curCol;
if (testMove(ctxMatrix, curRow, curCol, nxtRow, nxtCol))
{
// we have new updates, so expand more
expandCell(ctxMatrix, nxtRow, nxtCol);
}
// move left
nxtRow = curRow;
nxtCol = curCol-1;
if (testMove(ctxMatrix, curRow, curCol, nxtRow, nxtCol))
{
// we have new updates, so expand more
expandCell(ctxMatrix, nxtRow, nxtCol);
}
// move right
nxtRow = curRow;
nxtCol = curCol+1;
if (testMove(ctxMatrix, curRow, curCol, nxtRow, nxtCol))
{
// we have new updates, so expand more
expandCell(ctxMatrix, nxtRow, nxtCol);
}
}
public:
int minTime(vector<string> m, int startRow, int startCol, int endRow, int endCol)
{
row = m.size();
col = m[0].size();
ContextMatrix ctxMatrix;
initContextMatrix(ctxMatrix, m);
Context& startCtx = ctxMatrix[startRow-1][startCol-1];
startCtx.minute=1;
startCtx.reachingCost = startCtx.cost;
//start expanding from starting point
expandCell(ctxMatrix, startRow, startCol);
// now check the result
Context& ctx = ctxMatrix[endRow - 1][endCol - 1];
if (ctx.minute == 0)
{
// it cannot be reached...
return -1;
}
return ctx.minute;
}
};
int main()
{
ExpensiveTravel travel;
vector<string> m;
/*
m.push_back(string("452232"));
m.push_back(string("287979"));
m.push_back(string("219872"));
m.push_back(string("928234"));
m.push_back(string("767676"));
*/
m.push_back(string("123456789987654321"));
cout << travel.minTime(m, 1, 2, 1, 16) << endl;
}