จุดเริ่มต้นขั้นต่ำเพื่อไปถึงจุดหมายปลายทาง

ในการเริ่มต้นจากมุมบนซ้ายของตารางที่กำหนด จะต้องไปถึงมุมขวาล่าง แต่ละเซลล์ในตารางประกอบด้วยตัวเลข ตัวเลขอาจเป็นบวกหรือลบ เมื่อบุคคลไปถึงเซลล์ (i, j) จำนวนโทเค็นที่เขามี อาจเพิ่มขึ้นหรือลดลงพร้อมกับค่าของเซลล์นั้น เราต้องหาจำนวนโทเค็นเริ่มต้นขั้นต่ำที่จำเป็นในการเดินทางให้เสร็จสิ้น

มีกฎบางอย่าง -

• เราจะย้ายไปทางขวาหรือด้านล่างก็ได้
• เราไม่สามารถย้ายไปยังเซลล์ (i, j) หากโทเค็นรวมของเรามีค่าน้อยกว่า (i, j)
• เราต้องไปให้ถึงจุดหมายด้วยคะแนนบวกขั้นต่ำ

อินพุตและเอาต์พุต

Input:
The token for each room as a matrix.
-2  -3  3
-5 -10  1
10  30 -5

Output:
The minimum token required to start the journey. For this example, the required token is 7.

อัลกอริทึม

minInitTokens(matrix)

ป้อนข้อมูล: เมทริกซ์โทเค็นสำหรับแต่ละห้อง

ผลลัพธ์ − โทเค็นขั้นต่ำที่จำเป็นในการไปถึงจุดเริ่มต้นไปยังปลายทาง

Begin
   define matrix minToken of size same as matrix
   m := number of rows in matrix
   n := number of columns in matrix

   if matrix[m-1, n-1] > 0, then
      minToken[m-1, n-1] := 0
   else
      minToken[m-1, n-1] := 1 + absolute value of matrix[m-1, n-1]

   for i := m-2 down to 0, do
      minToken[i, n-1] := maximum of 1 and (minToken[i+1, n-1]-matrix[i,n-1])
   done

   for j := n-2 down to 0, do
      minToken[m-1, j] := maximum of 1 and (minToken[m-1, j+1]-matrix[m-1, j])
   done

   for i := m-2 down to 0, do
      for j := n-2 down to 0, do
         rem := minimum of minToken[i+1, j] and minToken[i, j+1]
         minPoint[i, j] := maximum of 1 and (rem – matrix[i,j])
      done
   done

   return minToken[0, 0]
End

ตัวอย่าง

#include<iostream>
#include<cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
   {-2,-3,3},
   {-5,-10,1},
   {10,30,-5}
};

int max(int a, int b) {
   return (a>b)?a:b;
}

int minInitPoints() {
   int minToken[ROW][COL];
   int m = ROW, n = COL;
   
   minToken[m-1][n-1] = tokens[m-1][n-1] > 0? 1: abs(tokens[m-1][n-1]) + 1;
   
   for (int i = m-2; i >= 0; i--)    //from last row to first row, fill points
      minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);
   
   for (int j = n-2; j >= 0; j--)    //fill last column to first column, fill points
      minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

   for (int i=m-2; i>=0; i--) {
      for (int j=n-2; j>=0; j--) {
         int remPoint = min(minToken[i+1][j], minToken[i][j+1]);    //calculate remaining points
         minToken[i][j] = max(remPoint - tokens[i][j], 1);
      }
   }
   return minToken[0][0];
}

int main() {
   cout << "Minimum Points Required: " << minInitPoints();
}

ผลลัพธ์

Minimum Points Required: 7