จำนวนเมทริกซ์ย่อยที่รวมไปยังเป้าหมายใน C++

สมมติว่าเรามีเมทริกซ์และค่าเป้าหมาย เราต้องหาจำนวน non-emptysubmatrices ที่ผลรวมเท่ากับเป้าหมาย ในที่นี้เมทริกซ์ย่อย [(x1, y1), (x2, y2)] คือชุดของเมทริกซ์เซลล์ทั้งหมด[x][y] ที่มี x ในช่วง x1 และ x2 และ y ในช่วง y1 และ y2 เมทริกซ์ย่อยสองรายการ [(x1, y1), (x2, y2)] และ [(x1', y1'), (x2', y2')] จะต่างกันหากมีพิกัดที่แตกต่างกัน เช่น ถ้า x1 ไม่ใช่ เท่ากับ x1'.

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

และเป้าหมาย =0 ดังนั้นผลลัพธ์จะเป็น 4 เนื่องจากเมทริกซ์ย่อย 1x1 สี่ตัวที่มีเพียง 0 เท่านั้น

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

• ตอบ :=0

• col :=จำนวนคอลัมน์

• แถว :=จำนวนแถว

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

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

    • เมทริกซ์[i, j] :=เมทริกซ์[i, j] + เมทริกซ์[i, j - 1]

• กำหนดหนึ่งแผนที่ m

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

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

    • เคลียร์แผนที่ ม

    • ม[0] :=1

    • ผลรวม :=0

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

    • ปัจจุบัน :=matrix[k, j]

    • ถ้า i - 1>=0 แล้ว −

      • ปัจจุบัน :=ปัจจุบัน - matrix[k, i - 1]

    • ผลรวม :=ผลรวม + ปัจจุบัน

    • ans :=ans + m[target - sum]

    • เพิ่ม m[-sum] ขึ้น 1

• กลับมาอีกครั้ง

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

ตัวอย่าง

#include ใช้เนมสเปซ std;class Solution { สาธารณะ:int numSubmatrixSumTarget (เวกเตอร์ <เวกเตอร์ >&เมทริกซ์ int เป้าหมาย) { int ans =0; int col =เมทริกซ์[0].size(); แถว int =matrix.size(); for(int i =0; i  m; for(int i =0; i =0)current -=matrix[k][i - 1]; ผลรวม +=ปัจจุบัน; ans +=m[เป้าหมาย - ผลรวม]; ม[-ผลรวม]++; } } } ส่งคืน ans; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{0,1,0},{1,1,1},{0,1,0}}; cout <<(ob.numSubmatrixSumTarget(v, 0));}

อินพุต

ผลลัพธ์

4