778 .上水で泳ぐ

10436 ワード
algorithms 100daysofcode programming cpp テキストリンク

778 .上水で泳ぐ


説明


この値はn x n°であり、その値242479142・・・は、24479142・142である.
雨が降り始めた.時間gridでは、水の深さは242479142である.正方形から別の4方向に隣接した正方形の場合、両方の正方形の標高が個別に最大grid[i][j]である場合のみ、泳ぐことができます.ゼロの時間で無限の距離を泳ぐことができます.もちろん、あなたの水泳中にグリッドの境界の中に滞在する必要があります.
左上角(i, j)で始まる場合は、右下角242479142度に達するまで最低時間を返します.

例1 :


Untitled
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

例2 :


Untitled
Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

制約

  • t
  • t
  • t
  • (n - 1, n - 1)
  • 各値は(0, 0) .

    • 解決策


    解決方法1


    直観

  • バイナリ検索
    • 左上から右下まで行くかどうかチェックするために、
  • DFS?

    • コード


    class Solution {
public:
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    int n;
    vector<vector<int>> g;
    vector<vector<bool>> visited;

    bool dfs(int x, int y, int elevation) {
        if (x == n - 1 && y == n - 1) return true;
        visited[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int i = x + dx[k], j = y + dy[k];
            if (i >= 0 && i < n && j >= 0 && j < n && g[i][j] <= elevation && !visited[i][j] && dfs(i, j, elevation))
                return true;
        }
        return false;
    }

    bool check(int elevation) {
        if (g[0][0] > elevation) return false;
        visited = vector<vector<bool>>(n, vector<bool>(n, false));
        return dfs(0, 0, elevation);
    }

    int swimInWater(vector<vector<int>>& grid) {
        g = grid;
        n = grid.size();
        int l = 0, r = n * n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

    複雑さ

  • 時間:O(nlogn)
  • スペース: O ( n )

    • ソリューション2


    直観


    コード

    複雑さ

  • 時間:
  • スペース:

    • 類似の質問

    HeadFirst Java研究(7.継承、多形性)
    webpack