Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

คะแนนสูงสุดที่รวบรวมโดยสองคนที่อนุญาตให้พบกันครั้งเดียวใน C++


ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อค้นหาคะแนนสูงสุดที่รวบรวมโดยบุคคลสองคนที่ได้รับอนุญาตให้พบกันครั้งเดียว

สำหรับสิ่งนี้เราจะได้รับเมทริกซ์ที่มีเซลล์ที่มีจุด งานของเราคือค้นหาเส้นทางเมื่อคนสองคนที่เริ่มต้นจากสองมุมมาบรรจบกันเพื่อที่พวกเขาจะได้รับคะแนนสูงสุด

ตัวอย่าง

#include<bits/stdc++.h>
#define M 3
#define N 3
using namespace std;
int findMaxPoints(int A[][M]) {
   //storing points
   int P1S[M+1][N+1], P1E[M+1][N+1];
   memset(P1S, 0, sizeof(P1S));
   memset(P1E, 0, sizeof(P1E));
   int P2S[M+1][N+1], P2E[M+1][N+1];
   memset(P2S, 0, sizeof(P2S));
   memset(P2E, 0, sizeof(P2E));
   for (int i=1; i<=N; i++)
      for (int j=1; j<=M; j++)
         P1S[i][j] = max(P1S[i-1][j], P1S[i][j-1]) + A[i-1][j-1];
   for (int i=N; i>=1; i--)
      for (int j=M; j>=1; j--)
         P1E[i][j] = max(P1E[i+1][j], P1E[i][j+1]) + A[i-1][j-1];
   for (int i=N; i>=1; i--)
      for(int j=1; j<=M; j++)
         P2S[i][j] = max(P2S[i+1][j], P2S[i][j-1]) + A[i-1][j-1];
   for (int i=1; i<=N; i++)
      for (int j=M; j>=1; j--)
         P2E[i][j] = max(P2E[i-1][j], P2E[i][j+1]) + A[i-1][j-1];
   int ans = 0;
   for (int i=2; i<N; i++) {
      for (int j=2; j<M; j++) {
         int op1 = P1S[i][j-1] + P1E[i][j+1] + P2S[i+1][j] + P2E[i-1][j];
         int op2 = P1S[i-1][j] + P1E[i+1][j] + P2S[i][j-1] + P2E[i][j+1];
         ans = max(ans, max(op1, op2));
      }
   }
   return ans;
}
int main() {
   int A[][M] = {
      {100, 100, 100},
      {100, 1, 100},
      {100, 100, 100}
   };
   cout << "Max Points : " << findMaxPoints(A);
   return 0;
}

ผลลัพธ์

Max Points : 800