ระยะทางที่สั้นที่สุดจากอาคารทั้งหมดใน C++

สมมติว่าเราต้องการสร้างบ้านบนที่ดินเปล่าซึ่งเข้าถึงอาคารทั้งหมดได้ในระยะทางที่สั้นที่สุด เราขยับได้เพียงสี่ทิศทางเท่านั้น เช่น ขึ้น ลง ซ้ายและขวา เรามีตาราง 2 มิติของค่า 0, 1 หรือ 2 โดยที่ −

• 0 หมายถึง ดินแดนที่ว่างเปล่าซึ่งเราสามารถผ่านไปได้โดยเสรี

• 1 หมายถึงสิ่งปลูกสร้างที่เราไม่สามารถผ่านได้

• 2 หมายถึง อุปสรรคที่เราไม่สามารถผ่านได้

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

แล้วเอาท์พุตจะเป็น 7 เนื่องจากให้อาคารสามหลังอยู่ที่ (0,0), (0,4), (2,2) และมีสิ่งกีดขวางอยู่ที่ (0,2) ดังนั้นจุด (1,2) จึงเป็น ที่ดินเปล่าเหมาะสร้างบ้าน ระยะทางรวม 3+3+1=7 เป็นอย่างต่ำ

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

• ret :=inf

• n :=ขนาดแถวของกริด

• m :=ขนาด col ของกริด

• numberOfOnes :=0

• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่งขนาด n x m

• กำหนดขอบเขตอาร์เรย์ 2 มิติหนึ่งขนาด n x m

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

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

    • ถ้า grid[i, j] เหมือนกับ 1 แล้ว −

      • (เพิ่มจำนวนคนขึ้น 1)

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

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

      • กำหนดการเยี่ยมชมหนึ่งชุด

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

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

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

          • curr :=องค์ประกอบแรกของ q

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

          • x :=curr.first

          • y :=curr.วินาที

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

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

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

            • ถ้า nx และ ny อยู่ในช่วงของกริด orgrid[nx,ny] ไม่ใช่ 0 ดังนั้น

            • ไม่ต้องสนใจตอนต่อไป ข้ามไปตอนต่อไป

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

            • dist[nx, ny] :=dist[nx, ny] + เลเวล

            • (เพิ่มการเข้าถึง[nx, ny] 1)

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

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

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

    • ถ้า grid[i, j] เท่ากับ 0 และ reach[i, j] เหมือนกับ numberOfOnes แล้ว −

      • ret :=ขั้นต่ำของ ret และ dist[i, j]

• return (ถ้า ret เหมือนกับ inf แล้ว -1 มิฉะนั้น ret)

ตัวอย่าง

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

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   int shortestDistance(vector<vector<int>>& grid) {
      int ret = INT_MAX;
      int n = grid.size();
      int m = grid[0].size();
      int numberOfOnes = 0;
      vector < vector <int> > dist(n, vector <int>(m));
      vector < vector <int> > reach(n, vector <int>(m));
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 1){
               numberOfOnes++;
               queue < pair <int, int> > q;
               q.push({i, j});
               set < pair <int, int> > visited;
               for(int lvl = 1; !q.empty(); lvl++){
                  int sz = q.size();
                  while(sz--){
                     pair <int, int> curr = q.front();
                     q.pop();
                     int x = curr.first;
                     int y = curr.second;
                     for(int k = 0; k < 4; k++){
                        int nx = x + dir[k][0];
                        int ny = y + dir[k][1];
                        if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
                        visited.insert({nx, ny});
                        dist[nx][ny] += lvl;
                        reach[nx][ny]++;
                        q.push({nx, ny});
                     }
                  }
               }
            }
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
               ret = min(ret, dist[i][j]);
            }
         }
      }
      return ret == INT_MAX ? -1 : ret;
   }
};

อินพุต

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

ผลลัพธ์

7