목적지에 도달하기 위한 최소 초기 포인트

주어진 그리드의 왼쪽 상단 모서리에서 시작하려면 오른쪽 하단 모서리에 도달해야 합니다. 그리드의 각 셀에는 숫자가 포함되며 숫자는 양수 또는 음수일 수 있습니다. 사람이 셀(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