เส้นที่ยาวที่สุดในเมทริกซ์ใน C++

สมมติว่าเรามีเมทริกซ์ไบนารี M หนึ่งเส้น เราต้องหาเส้นที่ยาวที่สุดในเมทริกซ์นั้น เส้นอาจเป็นแนวนอน แนวตั้ง เส้นทแยงมุม หรือแนวทแยง

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 3

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

• ยกเลิก :=0

• n :=แถวของ M

• m :=คอลัมน์ของ M

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

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <4 อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

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

    • ret :=สูงสุดของ ret และ dp[0, i, j]

• สำหรับการเริ่มต้น j :=0 เมื่อ j

  • ถ้า M[0, j] ไม่ใช่ศูนย์และ j> 0 แล้ว −

    • dp[0, j, 1] :=1 + dp[0, j - 1, 1]

    • ret :=สูงสุดของ ret และ dp[0, j, 1]

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • dp[i, j, 0] :=(ถ้า M[i, j] ไม่ใช่ศูนย์ ดังนั้น 1 + dp[i - 1, j, 0] มิฉะนั้น 0)

    • ถ้า j> 0 แล้ว −

      • dp[i, j, 1] :=(ถ้า M[i, j] ไม่ใช่ศูนย์ ดังนั้น dp[i, j - 1, 1] + 1 มิฉะนั้น 0)

      • dp[i, j, 2] :=(ถ้า M[i, j] ไม่ใช่ศูนย์ ดังนั้น dp[i - 1, j - 1, 2] + 1 มิฉะนั้น 0)

    • มิฉะนั้น

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

      • dp[i, j, 2] :=M[i, j]

    • ถ้า j + 1

      • dp[i, j, 3] :=(ถ้า M[i, j] ไม่ใช่ศูนย์ ดังนั้น dp[i - 1, j + 1, 3] + 1 มิฉะนั้น 0)

    • มิฉะนั้น

      • dp[i, j, 3] :=M[i, j]

    • สำหรับการเริ่มต้น k :=0 เมื่อ k <4 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

      • ret :=สูงสุดของ ret และ dp[i, j, k]

• รีเทิร์น

ตัวอย่าง

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

#include ใช้เนมสเปซ std;class Solution {public:int longestLine(vector>&M) { int ret =0; int n =M.size(); int m =!n ? 0 :M[0].size(); vector<เวกเตอร์<เวกเตอร์>> dp(n, เวกเตอร์<เวกเตอร์>(m, เวกเตอร์(4))); สำหรับ (int i =0; i  0) { dp[0][j][1] =1 + dp[0][j - 1][1]; ret =สูงสุด (ret, dp[0][j][1]); } } for (int i =1; i  0) { dp[i][j][1] =M[i][j] ? dp[i][j - 1][1] + 1 :0; dp[i][j][2] =M[i][j] ? dp[i - 1][j - 1][2] + 1 :0; } อื่นๆ { dp[i][j][1] =M[i][j]; dp[i][j][2] =M[i][j]; } if (j + 1 > v ={{0,1,1,0},{0,1,1,0},{0,0,0,1}}; cout <<(ob.longestLine(v));}

อินพุต

ผลลัพธ์

3