จำนวนเส้นทางที่มีคะแนนสูงสุดใน C++

สมมติว่าเรามีกระดานอักขระสี่เหลี่ยม เราสามารถย้ายบนกระดานโดยเริ่มต้นที่สี่เหลี่ยมด้านล่างขวาที่มีอักขระ 'S' ตอนนี้เราต้องไปถึงช่องสี่เหลี่ยมด้านซ้ายบนที่มีอักขระ 'E' สี่เหลี่ยมอื่นๆ จะมีป้ายกำกับด้วยอักขระตัวเลขตั้งแต่ 1 ถึง 9 หรือมีเครื่องหมาย 'X' กีดขวาง ในจังหวะเดียวเราสามารถขึ้น ซ้าย หรือขึ้นซ้ายได้ก็ต่อเมื่อไม่มีสิ่งกีดขวางที่นั่น

เราต้องหารายการของตัวเลขสองตัว:หมายเลขแรกคือผลรวมสูงสุดของอักขระตัวเลขที่เรารวบรวมได้ และหมายเลขที่สองคือจำนวนเส้นทางที่เราสามารถทำได้เพื่อให้ได้ผลรวมสูงสุดนั้น สำหรับคำตอบ ให้คืนค่าเป็น modulo 10^9 + 7 เมื่อไม่มีเส้นทาง ให้กลับ [0, 0].

ดังนั้น หากอินพุตเป็นเหมือนบอร์ด =["E12","1X1","21S"] เอาต์พุตจะเป็น [1,2]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=จำนวนแถว, m :=จำนวนคอลัมน์

• กำหนดอาร์เรย์ 3 มิติของคำสั่ง n x m x 2 หนึ่งชุด

• dp[n - 1, m - 1, 0] =0, dp[n - 1, m - 1, 1] =1

• สำหรับการเริ่มต้น i :=m - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • ถ้า b[n - 1, i] เหมือนกับ ASCII ของ 'X' แล้ว −

    • dp[n - 1, i, 0] =b[n - 1, i] - ASCII ของ '0' + dp[n - 1, i + 1, 0]

  • dp[n - 1, i, 1] + =dp[n - 1, i + 1, 1]

• สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • ถ้า b[i, m - 1] เหมือนกับ ASCII ของ 'X' ดังนั้น −

    • dp[i, m - 1, 0] =b[i, m - 1] - ASCII ของ '0' + dp[i + 1, m - 1, 0]

  • dp[i, m - 1, 1] + =dp[i + 1, m - 1, 1]

• สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=m - 2 เมื่อ j>=0, อัปเดต (ลด j โดย 1) ให้ทำ -

    • ถ้า b[i, j] เหมือนกับ ASCII ของ 'X' แล้ว −

      • dp[i, j, 0] :=(ถ้า b[i, j] เหมือนกับ ASCII ของ 'E' แล้ว 0, มิฉะนั้น b[i, j] -ASCII ของ '0')

    • maxVal :=สูงสุดของ {dp[i, j + 1, 0], dp[i + 1, j, 0], dp[i + 1, j + 1, 0]}

    • ถ้า maxVal เท่ากับ 0 และ (b[i + 1, j] ไม่เท่ากับ ASCII ของ 'S' และ b[i, j + 1] ไม่เท่ากับ ASCII ของ 'S' และ b[i + 1 j + 1] ไม่เท่ากับ ASCII ของ 'S') ดังนั้น −

      • dp[i, j, 0] :=0

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • dp[i, j, 0] :=dp[i, j, 0] + maxVal

    • ถ้า dp[i + 1, j, 0] เหมือนกับ maxVal แล้ว −

      • dp[i, j, 1] :=dp[i, j, 1] + dp[i + 1, j, 1]

    • ถ้า dp[i + 1, j + 1, 0] เหมือนกับ maxVal แล้ว −

      • dp[i, j, 1] :=dp[i, j, 1] + dp[i + 1, j + 1, 1]

    • ถ้า dp[i, j + 1, 0] เหมือนกับ maxVal แล้ว −

      • dp[i, j, 1] :=dp[i, j, 1] + dp[i, j + 1, 1]

    • dp[i, j, 1] :=dp[i, j, 1] mod ม.

    • dp[i, j, 0] :=dp[i, j, 0] mod ม.

• กลับ dp[0, 0]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   } cout << "]"<<endl;
}
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
   return ((a % m) + (b % m) % m);
} class Solution {
   public:
   vector<int> pathsWithMaxScore(vector<string>& b) {
      int n = b.size();
      int m = b[0].size();
      vector < vector < vector <int> > > dp(n, vector < vector
      <int> >(m, vector <int> (2)));
      dp[n - 1][m - 1][0] = 0;
      dp[n - 1][m - 1][1] = 1;
      for(int i = m - 2; i >= 0; i--){
         if(b[n - 1][i] == 'X')break;
         dp[n - 1][i][0] = b[n - 1][i] - '0' + dp[n - 1][i + 1]
         [0];
         dp[n - 1][i][1] += dp[n - 1][i + 1][1];
      }
      for(int i = n - 2; i >= 0; i--){
         if(b[i][m - 1] == 'X')break;
         dp[i][m - 1][0] = b[i][m - 1] - '0' + dp[i + 1][m - 1]
         [0];
         dp[i][m - 1][1] += dp[i + 1][m - 1][1];
      }
      for(int i = n - 2; i >= 0; i--){
         for(int j = m - 2; j >= 0; j--){
            if(b[i][j] == 'X')continue;
            dp[i][j][0] = b[i][j] == 'E' ? 0 :b[i][j] - '0';
            int maxVal = max({dp[i][j + 1][0], dp[i + 1][j][0],
            dp[i + 1][j + 1][0]});
            if(maxVal == 0 && (b[i+1][j] != 'S' && b[i][j + 1] !
            = 'S' && b[i+1][j + 1] != 'S')){
               dp[i][j][0] = 0;
               continue;
            }
            dp[i][j][0] += maxVal;
            if(dp[i + 1][j][0] == maxVal){
               dp[i][j][1] += dp[i + 1][j][1];
            }
            if(dp[i + 1][j + 1][0] == maxVal){
               dp[i][j][1] += dp[i + 1][j + 1][1];
            }
            if(dp[i][j + 1][0] == maxVal){
               dp[i][j][1] += dp[i][j + 1][1];
            }
            dp[i][j][1] %= m;
            dp[i][j][0] %= m;
         }
      }
      return dp[0][0];
   }
};
main(){
   Solution ob;
   vector<string> v = {"E12","1X1","21S"};
   print_vector(ob.pathsWithMaxScore(v));
}

อินพุต

{"E12","1X1","21S"}

ผลลัพธ์

[1, 2, ]