生活随笔
收集整理的這篇文章主要介紹了
LeetCode 417 太平洋大西洋水流问题
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
題目描述
給定一個(gè) m x n 的非負(fù)整數(shù)矩陣來表示一片大陸上各個(gè)單元格的高度。“太平洋”處于大陸的左
邊界和上邊界，而“大西洋”處于大陸的右邊界和下邊界。規(guī)定水流只能按照上、下、左、右四個(gè)方向流動(dòng)，且只能從高到低或者在同等高度上流動(dòng)。請找出那些水流既可以流動(dòng)到“太平洋”，又能流動(dòng)到“大西洋”的陸地單元的坐標(biāo)。
題解
深度優(yōu)先搜索，可以反過來進(jìn)行思考，從大洋向內(nèi)地流。
代碼
class Solution {
public:void dfs(vector<vector<int>>& matrix,int x,int y,int m,int n,vector<vector<bool>>& f){f[x][y]=true;for (int k=0;k<4;k++){int xx=x+d[k][0];int yy=y+d[k][1];if (xx<0||yy<0||xx>=m||yy>=n) continue;if (!f[xx][yy]&&matrix[xx][yy]>=matrix[x][y]){dfs(matrix,xx,yy,m,n,f);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {int m=matrix.size();if (!m) return {};int n=matrix[0].size();vector<vector<bool>> f1(m,vector<bool>(n,false));vector<vector<bool>> f2(m,vector<bool>(n,false));for (int i=0;i<m;i++){dfs(matrix,i,0,m,n,f1);dfs(matrix,i,n-1,m,n,f2);}for (int j=0;j<n;j++){dfs(matrix,0,j,m,n,f1);dfs(matrix,m-1,j,m,n,f2);}vector<vector<int>> res;for (int i=0;i<m;i++){for (int j=0;j<n;j++){if (f1[i][j]&&f2[i][j]) res.push_back({i,j});}}return res;}int d[4][2]={0,1,0,-1,1,0,-1,0};
};
總結(jié)
以上是生活随笔 為你收集整理的LeetCode 417 太平洋大西洋水流问题 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
