Algorithm

 Problem Statement for ExpensiveTravel

problem link- https://community.topcoder.com/stat?c=problem_statement&pm=7337&rd=10659

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 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: String[], int, int, int, int
Returns: int
Method signature: int minTime(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

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

struct node {
  int x, y, num, den, m;
  node(int x, int y, int num, int den, int m) :
  x(x), y(y), num(num), den(den), m(m) {}
  bool operator<(const node &n) const {
    if(m != n.m)
      return m > n.m;
    return (1.0 * num / den) - 1e-9> (1.0 * n.num / n.den);
  }
};

pair<int, int> add(int num1, int den1, int num2, int den2) {
  int num = den1 * num2 + den2 * num1;
  int den = den1 * den2;
  int gcd = __gcd(num, den);
  return make_pair(num / gcd, den / gcd);
}

bool vis[51][51];
priority_queue<node> pq;

class ExpensiveTravel {
public:
  int minTime(vector<string> m, int startRow, int startCol, int endRow, int endCol) {
    --startRow, --startCol;
    --endRow, --endCol;
    if(m[startRow][startCol] == '1' || m[endRow][endCol] == '1')
      return -1;

    pq.push(node(startRow, startCol, 1, m[startRow][startCol] - '0', 0));

    while(!pq.empty()) {
      node fr = pq.top();
      pq.pop();

      if(vis[fr.x][fr.y])
        continue;
      vis[fr.x][fr.y] = true;

      if(fr.x == endRow && fr.y == endCol)
        return fr.m + 1;

      for(int i = 0, nx, ny; i < 4; ++i) {
        nx = fr.x + dx[i];
        ny = fr.y + dy[i];

        if(nx == fr.x && ny == fr.y)
          continue;

        if(nx < 0 || nx >= m.size() || ny < 0 || ny >= m[0].length() || m[nx][ny] == '1')
          continue;

        pair<int, int> frac = add(fr.num, fr.den, 1, m[nx][ny] - '0');

        if(frac.first > frac.second) {
          frac = add(1, m[fr.x][fr.y] - '0', 1, m[nx][ny] - '0');
          pq.push(node(nx, ny, frac.first, frac.second, fr.m + 1));
        } else
          pq.push(node(nx, ny, frac.first, frac.second, fr.m));
      }
    }

    return -1;
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{"22334"}
1
1
1
5

Output

x
–
+
cmd
3
Advertisements

Demonstration

TopCoder Solution SRM335-D1-500 Problem Statement for ExpensiveTravel C,C++, Java, Js and Python ,SRM335-D1-500,TopCoder Solution