Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 상승하는 물에서 수영하기

<시간/>

하나의 N x N 그리드가 있다고 가정하고 각 정사각형 그리드[i][j]는 해당 지점(i,j)에서의 고도를 나타냅니다. 이제 비가 내리기 시작했다고 생각해 보십시오. 시간 t에서 모든 곳의 수심은 t입니다. 두 정사각형의 높이가 개별적으로 최대 t일 때 정사각형에서 4방향으로 인접한 다른 정사각형으로 수영할 수 있습니다. 우리는 제로 시간에 무한한 거리를 수영할 수 있습니다.

(0, 0) 위치에서 시작해야 합니다. 오른쪽 아래 사각형(N-1, N-1)에 도달할 때까지 최소 시간을 찾아야 합니다.

따라서 입력이 다음과 같은 경우

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

올바른 방법은 색상입니다. 따라서 답은 16이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 데이터를 정의합니다. 여기에는 시간, x 및 y와 같은 세 가지 매개변수가 필요합니다.
  • 배열 디렉토리 크기 정의:4 x 2 :={ { 1, 0 }, { - 1, 0 }, { 0, 1 }, { 0, - 1 } }
  • n :=그리드의 행, m :=그리드의 열
  • 우선순위 대기열 q 정의
  • 방문한 크기가 n x m인 하나의 2D 배열을 정의하고 0으로 채웁니다.
  • 방문함[0, 0] :=1
  • q에 데이터(그리드[0, 0], 0, 0) 삽입
  • 동안(q가 비어 있지 않음) −
    • 노드 =q의 최상위 요소 및 q에서 요소 삭제
    • time :=노드의 시간
    • x :=노드의 x, y :=노드의 y
    • x가 n - 1과 같고 y가 m - 1과 같으면 −
      • 반환 시간
    • 초기화 i의 경우:=0, i <4일 때 업데이트(i 1만큼 증가), 수행 -
      • nx :=dir[i, 0] + x, ny :=dir[i, 1] + y
      • nx>=0이고 nx =0이고 ny
      • 방문함[nx, y] :=1
      • q에 데이터(그리드[nx, ny] 및 시간, nx, ny의 최대값) 삽입
  • 반환 -1

    • 이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

    예시

    #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));
}

    입력

    {{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}}

    출력

    16