Computer >> Máy Tính >  >> Lập trình >> C ++

Bơi trong nước dâng trong C ++

Giả sử chúng ta có một lưới N x N, mỗi ô vuông [i] [j] đại diện cho độ cao tại điểm đó (i, j). Bây giờ coi như trời đã bắt đầu mưa. Tại thời điểm t, độ sâu của nước ở mọi nơi là t. Chúng ta có thể bơi từ một hình vuông sang một hình vuông liền kề 4 hướng khác khi độ cao của cả hai hình vuông riêng lẻ là t. Chúng ta có thể bơi khoảng cách vô hạn trong thời gian không.

Chúng ta nên bắt đầu từ vị trí (0, 0). Chúng tôi phải tìm thời gian ít nhất cho đến khi chúng tôi có thể đến hình vuông dưới cùng bên phải (N-1, N-1)

Vì vậy, nếu đầu vào giống như

0 1 2 3 4
24 23 22 21 5
12 13 15 15 16
11 17 18 19 20
10 9 8 7 6

Cách chính xác được tô màu. Vì vậy, câu trả lời sẽ là 16.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định Dữ liệu, điều này sẽ sử dụng ba tham số như thời gian, x và y.
  • Xác định một dir mảng có kích thước:4 x 2:={{1, 0}, {- 1, 0}, {0, 1}, {0, - 1}}
  • n:=hàng lưới, m:=cột lưới
  • xác định hàng đợi ưu tiên q
  • Xác định một mảng 2D được truy cập có kích thước n x m, điền vào mảng này bằng 0
  • đã ghé thăm [0, 0]:=1
  • chèn Dữ liệu (lưới [0, 0], 0, 0) vào q
  • while (không phải q trống), do -
    • node =phần tử trên cùng của q và xóa phần tử khỏi q
    • thời gian:=thời gian của nút
    • x:=x của nút, y:=y của nút
    • nếu x giống với n - 1 và y giống với m - 1 thì -
      • thời gian quay lại
    • để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -
      • nx:=dir [i, 0] + x, ny:=dir [i, 1] + y
      • nếu nx> =0 và nx =0 và ny
      • đã ghé thăm [nx, y]:=1
      • chèn Dữ liệu (tối đa lưới [nx, ny] và thời gian, nx, ny) vào q
  • trả về -1

    • Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

    Ví dụ 

    #include <bits/stdc++.h>
using namespace std;
struct Data{
   int time, x, y;
   Data(int a, int b, int y){
      time = a;
      x = b;
      this->y = y;
   }
};
struct Comparator{
   bool operator()(Data a, Data b){
      return !(a.time < b.time);
   }
};
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   int swimInWater(vector<vector<int>>& grid) {
      int n = grid.size();
      int m = grid[0].size();
      priority_queue <Data, vector <Data>, Comparator> q;
      vector < vector <int> > visited(n, vector <int>(m, 0));
      visited[0][0] = 1;
      q.push(Data(grid[0][0], 0, 0));
      while(!q.empty()){
         Data node = q.top();
         q.pop();
         int time = node.time;
         int x = node.x;
         int y = node.y;
         if(x == n - 1 && y == m - 1)return time;
         for(int i = 0; i < 4; i++){
            int nx = dir[i][0] + x;
            int ny = dir[i][1] + y;
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]){
               visited[nx][y] = 1;
               q.push(Data(max(grid[nx][ny], time), nx, ny));
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},   {10,9,8,7,6}};
   cout << (ob.swimInWater(v));
}

    Đầu vào 

    {{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},{10,9,8,7,6}}

    Đầu ra 

    16