แม็กซิมอลสแควร์ใน C++

สมมติว่าเรามีเมทริกซ์ไบนารี 2D ที่เต็มไปด้วย 0 และ 1 เราต้องหาสี่เหลี่ยมที่ใหญ่ที่สุดที่มีเพียง 1 แล้วคืนค่าพื้นที่ ดังนั้นหากเมทริกซ์เป็นเหมือน −

จากนั้นผลลัพธ์จะเป็น 4

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

• ans :=0, n :=จำนวนแถว, c :=จำนวนแถว

• ถ้า n เป็น 0 ให้คืนค่า 0

• สร้างเมทริกซ์ลำดับอื่น (n x c)

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • สำหรับ j ในช่วง 0 ถึง c – 1

    • m[i, j] :=matrix[i, j]

    • ans :=สูงสุดของ m[i, j] และ ans

• สำหรับ j ในช่วง 0 ถึง c – 1

  • ถ้า m[i, j] ไม่ใช่ 0 แล้ว

    • m[i, j] :=1 + ขั้นต่ำของ m[i + 1, j], m[i, j-1], m[i + 1, j-1],

  • ans :=สูงสุดของ m[i, j] และ ans

• กลับ ans*ans

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

ตัวอย่าง

#include ใช้เนมสเปซ std;class Solution { สาธารณะ:int maximalSquare (vector >&matrix) { int ans =0; int n =matrix.size(); if(!n) คืนค่า 0; int c =เมทริกซ์[0].size(); เวกเตอร์<เวกเตอร์> m(n, เวกเตอร์  (c)); สำหรับ(int i =0;i=0;i--){ for(int j =1;j> v ={{'1','0','1','0','0'},{'1','0','1 ','1','1'},{'1','1','1','1','1'}, {'1','0','0','1', '0'}}; โซลูชัน ob; ศาล <<((ob.maximalSquare(v)));}

อินพุต

ผลลัพธ์

4