01 เมทริกซ์ใน C++

สมมติว่าเรามีเมทริกซ์ที่ประกอบด้วย 0 และ 1 เราต้องหาระยะทางของ 0 ที่ใกล้ที่สุดสำหรับแต่ละเซลล์ ในที่นี้ระยะห่างระหว่างสองเซลล์ที่อยู่ติดกันคือ 1

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

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

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

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

• n :=จำนวนแถว m :=จำนวนคอลัมน์

• กำหนดหนึ่งเมทริกซ์ ret of order (n x m) และเติมด้วย inf

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

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

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

    • ถ้าไม่ใช่เมทริกซ์[i, j] จะไม่ใช่ศูนย์ ดังนั้น −

      • ret[i, j] :=0

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

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

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

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

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

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

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

      • nx :=curr.first + dir[k, 0]

      • ny :=curr.second + dir[k, 1]

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

        • ret[nx, ny] :=เลเวล

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

• รีเทิร์น

ตัวอย่าง

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

#include ใช้เนมสเปซ std;void print_vector(vector> v){ cout <<"["; for(int i =0; i> updateMatrix(vector>&matrix) { int n =matrix.size(); int m =เมทริกซ์[0].size(); เวกเตอร์ <เวกเตอร์ > ret(n, เวกเตอร์ (m, INT_MAX)); คิว <คู่ > q; for(int i =0; i  curr =q.front(); q.ป๊อป(); สำหรับ (int k =0; k <4; k++) { int nx =curr.first + dir[k][0]; int ny =curr.วินาที + dir[k][1]; if(nx <0 || nx>=n || ny <0 || ny>=m || ret[nx][ny] > v ={{0,0,0},{0,1,0},{1,1,1}}; print_vector(ob.updateMatrix(v));}

อินพุต

ผลลัพธ์

[[0, 0, 0, ],[0, 1, 0, ],[1, 2, 1, ],]