โปรแกรมหาปริมาณน้ำฝนที่จะจับระหว่างหุบเขาใน C++

สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยองค์ประกอบต่างๆ แสดงถึงความสูงของภูมิประเทศ ลองนึกภาพสถานการณ์ที่ฝนจะตกและพื้นที่ทั้งหมดในหุบเขาจะเต็มไป

เราต้องหาปริมาณฝนที่จะตกลงมาระหว่างหุบเขา

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

จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถเก็บน้ำได้ 3 หน่วยระหว่าง 4 ถึง 5 สี่เหลี่ยม

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

• กำหนดโครงสร้างข้อมูลที่มีพิกัด x และ y และความสูง h

• กำหนดลำดับความสำคัญของคิว pq จะจัดเก็บรายการข้อมูลที่จัดเรียงตามค่าความสูง

• n :=ขนาดของ h

• ถ้า n ไม่ใช่ศูนย์ ดังนั้น −

  • คืนค่า 0

• m :=ขนาดของ h[0]

• กำหนดคู่หนึ่งชุดที่เรียกว่าเยี่ยมชมแล้ว

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

  • แทรกข้อมูลใหม่ (h[i, 0], i, 0) ลงใน pq

  • แทรก {i, 0} เข้าไปแล้ว

  • แทรกข้อมูลใหม่ (h[i, m - 1], i, m - 1) ลงใน pq

  • แทรก {i, m - 1} เข้าไปแล้ว

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

  • แทรกข้อมูลใหม่ (h[0, i], 0, i) ลงใน pq

  • แทรก {0, i} เข้าไปแล้ว

  • แทรกข้อมูลใหม่ (h[n - 1, i], n - 1, i) ลงใน pq

  • แทรก {n - 1, i} เข้าไปแล้ว

• ยกเลิก :=0

• maxVal :=0

• ในขณะที่ pq ไม่ว่างเปล่า ให้ทำ -

  • temp =องค์ประกอบด้านบนของ pq

  • ลบองค์ประกอบด้านบนออกจาก pq

  • maxVal :=สูงสุดของความสูงของอุณหภูมิและ maxVal

  • x :=x อุณหภูมิ

  • y :=y ของอุณหภูมิ

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

    • nx :=x + dir[i, 0]

    • ny :=y + dir[i, 1]

    • ถ้า nx>=0 และ ny>=0 และ nx

      • val :=h[nx, ny]

      • ถ้าวาล

        • ret :=ret + maxVal - วาล

        • val :=maxVal

      • แทรกข้อมูลใหม่ (val, nx, ny) ลงใน pq

      • แทรก {nx, ny} เข้าไปแล้ว

• รีเทิร์น

ตัวอย่าง

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

#include ใช้เนมสเปซ std;จัดโครงสร้างข้อมูล { int x, y; int ชั่วโมง; ข้อมูล (int a, int b, int c) { h =a; x =ข; y =ค; }};struct Comparator { ตัวดำเนินการบูล () (ข้อมูล a, ข้อมูล b) { return !(ah >&h) {priority_queue, Comparator> pq; int n =h.size(); ถ้า (!n) คืนค่า 0; int m =h[0].size(); set> เยี่ยมชม; สำหรับ (int i =0; i =0 &&ny>=0 &&nx >&เมทริกซ์) { return (new Solution())->solve(matrix);}int main(){ vector> v ={ {6, 6, 6, 8}, {6, 4, 5, 8}, {6, 6, 6, 6} }; ศาล <<แก้ (v);}

อินพุต

ผลลัพธ์

3