ไกลจากแผ่นดินเท่าที่เป็นไปได้ใน C++

สมมติว่าเรามีตาราง N x N หนึ่งตารางที่มีค่าเท่านั้น เช่น 0 และ 1 โดยที่ 0 หมายถึงน้ำ และ 1 หมายถึงพื้นดิน เราต้องหาเซลล์น้ำเพื่อให้ระยะห่างจากเซลล์ภาคพื้นดินที่ใกล้ที่สุดขยายใหญ่สุดและส่งกลับระยะทาง เราจะใช้ระยะทางแมนฮัตตัน − ระยะห่างระหว่างสองเซลล์ (x0, y0) และ (x1, y1) คือ |x0 - x1| + |y0 - y1|. หากไม่มีดินหรือน้ำอยู่ในกริด ให้คืนค่า -1

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากเซลล์ (1,1) อยู่ไกลที่สุดจากพื้นดินทั้งหมดที่มีระยะทาง 2

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

• dir :=[(1, 0), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1), (0, 1) , (0, -1)]

• dir2 :=[(1, 0), (-1, 0), (0, 1), (0, -1)]

• กำหนดแผนที่ ม. กำหนดคิวคิว n :=จำนวนแถวและ c :=จำนวนคอลัมน์

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • สำหรับ j ในช่วง 0 ถึง n – 1

    • ถ้า grid[i, j] เป็น 1 ให้ใส่คู่ (i, j) ลงใน q แล้วใส่ m[(i, j)] :=(j ,i)

• ถอยหลัง :=-1

• ในขณะที่ q ไม่ว่างเปล่า

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

  • ในขณะที่ sz ไม่ใช่ 0

    • temp :=องค์ประกอบแรกของ q ลบองค์ประกอบแรกออกจาก q

    • สำหรับ k ในช่วง 0 ถึง 3 −

      • nx :=ค่าแรกของ temp + dir2[k, 0]

      • ny :=ค่าที่สองของ temp + dir2[k, 1]

      • ถ้า nx และ ny ไม่อยู่ในช่วงของ grid หรือ grid[nx, ny] คือ 1 ให้ข้ามไปที่การวนซ้ำถัดไป

      • m[(nx, ny)] :=m[temp]

      • ret :=max of (ระยะทางของ (nx, ny) และ m(temp)) และ ret

      • แทรก (nx,ny) ลงใน q

      • ตั้งค่ากริด[nx, ny] :=1

    • ลด sz ลง 1

• รีเทิร์น

ตัวอย่าง(C++)

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

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {
   {1, 0}, {-1, 0}, {1, -1}, {1, 1},
   {-1, 1}, {-1, -1}, {0, 1}, {0, -1}
};
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   int calcDist(int x1, int y1, int x2, int y2){
      return abs(x1 - x2) + abs(y1 - y2);
   }
   int maxDistance(vector<vector<int>>& grid) {
      map < pair <int, int>, pair <int, int> > m;
      queue < pair <int, int> > q;
      int n = grid.size();
      int c = n? grid[0].size() : 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < c; j++){
            if(grid[i][j] == 1){
               q.push({i, j});
               m[{i, j}] = {i, j};
            }
         }
      }
      int ret = -1;
      while(!q.empty()){
         int sz = q.size();
         while(sz--){
            pair <int, int> temp = q.front();
            q.pop();
            for(int k = 0; k < 4; k++){
               int nx = temp.first + dir2[k][0];
               int ny = temp.second + dir2[k][1];
               if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;
               m[{nx, ny}] = m[temp];
               ret = max(calcDist(nx, ny, m[temp].first,
               m[temp].second), ret);
               q.push({nx, ny});
               grid[nx][ny] = 1;
            }
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
   Solution ob;
   cout << (ob.maxDistance(v1));
}

อินพุต

["alice,20,800,mtv","bob,50,1200,mtv"]

ผลลัพธ์

2