กำแพงและประตูในภาษา C++

สมมติว่าเรามีกริด 2 มิติขนาด 1 ม. x น. และนั่นเริ่มต้นด้วยค่าที่เป็นไปได้สามค่านี้

• -1 สำหรับกำแพงหรือสิ่งกีดขวาง

• 0 สำหรับเกท

• INF นี่คืออินฟินิตี้หมายถึงห้องว่าง

ที่นี่ 2^31 - 1 =2147483647 คือ INF เนื่องจากเราอาจสมมติได้ว่าระยะทางไปยังประตูหนึ่งมีค่าน้อยกว่า 2147483647 เติมแต่ละห้องว่างด้วยระยะทางไปยังประตูที่ใกล้ที่สุด หากเข้าถึงประตูไม่ได้ก็ควรเติม INF

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

แล้วผลลัพธ์ที่ได้จะเป็น

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

• กำหนดขนาดอาร์เรย์ของขนาด:4 x 2 :={{1, 0}, {-1, 0}, {0, 1}, {0,-1}}

• n :=ขนาดห้อง

• m :=(ถ้า n ไม่ใช่ศูนย์ ให้นับคอลัมน์ มิฉะนั้น 0)

• กำหนดหนึ่งคิว q ของคู่

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

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

    • ถ้าห้อง[i, j] เท่ากับ 0 แล้ว −

      • แทรก { i, j } ลงใน q

• สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -

  • sz :=ขนาดของ q

  • ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz ลง 1 ในการวนซ้ำแต่ละครั้ง ให้ทำ -

    • กำหนดหนึ่งคู่ curr :=องค์ประกอบแรกของ q

    • ลบองค์ประกอบออกจาก q

    • x :=curr.first

    • y :=curr.second

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

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

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

      • ถ้า nx <0 หรือ ny <0 หรือ nx>=n หรือ ny>=m หรือ rooms[nx, ny]

        • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

      • ห้อง[nx, ny] :=เลเวล

      • แทรก { nx, ny } ลงใน q

ตัวอย่าง

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

#include ใช้เนมสเปซ std;void print_vector(vector v){ cout <<"["; for(int i =0; i&rooms) { int n =rooms.size(); int m =n ? ห้อง[0].size() :0; คิว> q; สำหรับ (int i =0; i  curr =q.front(); q.ป๊อป(); int x =curr.first; int y =curr.second; สำหรับ (int i =0; i <4; i++) { int nx =x + dir[i][0]; int ny =y + dir[i][1]; ถ้า (nx <0 || ny <0 || nx>=n || ny>=m || rooms[nx][ny]  v ={{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647, -1}, {0,-1,2147483647,2147483647}}; โซลูชัน ob; ob.wallsAndGates(v); print_vector(v);}

อินพุต

ผลลัพธ์

[[3, -1, 0, 1, ], [2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4 , ],]