fork(2) download 
  1. //++
  2. // File Name:
  3. //      TwoRobotsMaxProfit.cpp
  4. //
  5. // AUTHOR: Kenneth Hu
  6. // VERSION STATUS: created @ Jan 23 2015
  7. //
  8. // Contents:
  9. //--
  10.  
  11. #include <iostream>
  12. #include <assert.h>
  13. using namespace std;
  14.  
  15. #define MAX_MATRIX_WIDTH      6
  16. #define MAX_MATRIX_HEIGHT     6
  17.  
  18. class Solution{
  19. public:
  20.     int calculateMaxProfit(const unsigned int **matrix, int width, int height) {
  21.         assert(width <= MAX_MATRIX_WIDTH);
  22.         assert(height <= MAX_MATRIX_HEIGHT);
  23.         if (width == 0 || height == 0)
  24.             return 0;
  25.  
  26.         mHeight = height;  mWidth = width;
  27.         static unsigned int resultArr[MAX_MATRIX_HEIGHT*MAX_MATRIX_WIDTH][MAX_MATRIX_HEIGHT*MAX_MATRIX_WIDTH];
  28.         unsigned int nextStepMaxProfit = 0;
  29.         int nextRobot1Pos = 0, nextRobot2Pos = 0, x1 = 0, x2 = 0, y1 = 0, y2 = 0;
  30.  
  31.         for (int robot1Pos = width * height - 1; robot1Pos >= 0; --robot1Pos) {
  32.             for (int robot2Pos = width * height - 1; robot2Pos >= 0; --robot2Pos){
  33.                 translateToMatrixPos(robot1Pos, x1, y1);
  34.                 translateToMatrixPos(robot2Pos, x2, y2);
  35.                 if (robot1Pos == robot2Pos)
  36.                     resultArr[robot1Pos][robot2Pos] = matrix[x1][y1];
  37.                 else
  38.                     resultArr[robot1Pos][robot2Pos] = matrix[x1][y1] + matrix[x2][y2];
  39.  
  40.                 nextStepMaxProfit = 0;
  41.                 for (int i = 0; i < 2; ++i) {
  42.                     for (int j = 0; j < 2; ++j) {
  43.                         nextRobot1Pos = getNext(robot1Pos, i);
  44.                         nextRobot2Pos = getNext(robot2Pos, j);
  45.                         if (nextRobot1Pos >= 0 && nextRobot2Pos >= 0 && resultArr[nextRobot1Pos][nextRobot2Pos] > nextStepMaxProfit)
  46.                             nextStepMaxProfit = resultArr[nextRobot1Pos][nextRobot2Pos];
  47.                     }
  48.                 }
  49.  
  50.                 resultArr[robot1Pos][robot2Pos] += nextStepMaxProfit;
  51.             }
  52.         }
  53.  
  54.         return resultArr[0][0];
  55.     }
  56.  
  57. private:
  58.     int    mHeight;
  59.     int    mWidth;
  60.  
  61.     int    getNext(int curPos, bool goDown = true) {
  62.         int x =0, y = 0, nextPos = 0;
  63.         translateToMatrixPos(curPos, x, y);
  64.         if (goDown) {
  65.             if (x + 1 >= mHeight) return -1;
  66.             return (x + 1) * mWidth + y;
  67.         }
  68.         if (y + 1 >= mWidth) return -1;
  69.         return curPos + 1;
  70.     }
  71.  
  72.     void translateToMatrixPos(int pos, int &x, int &y) {
  73.         x = pos / mWidth;
  74.         y = pos % mWidth;
  75.     }
  76. };
  77.  
  78.  
  79. int main() {
  80.     const unsigned int MATRIX_SIZE = 3;
  81.     const unsigned int r1[MATRIX_SIZE] = { 0, 0, 2 };
  82.     const unsigned int r2[MATRIX_SIZE] = { 0, 3, 2 };
  83.     const unsigned int r3[MATRIX_SIZE] = { 0, 1, 0 };
  84.     const unsigned int *matrix[MATRIX_SIZE] = { r1, r2, r3 };
  85.     Solution so;
  86.  
  87.     cout << "Max Profit for two robots is " << so.calculateMaxProfit(matrix, MATRIX_SIZE, MATRIX_SIZE) << endl;
  88.     return 0;
  89. }
Success #stdin #stdout 0s 3100KB
comments (?)
stdin 
Standard input is empty
stdout 
Max Profit for two robots is 8
https://ideone.com/fnC3de
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!