LintCode 778 给定一个m×n的非负矩阵代表一个大洲，矩阵的每个单元格的值代表此处的地形高度，矩阵的左边缘和上边缘是“太平洋”，下边缘和右边缘是“大西洋”。

本文主要是介绍LintCode 778 给定一个m×n的非负矩阵代表一个大洲，矩阵的每个单元格的值代表此处的地形高度，矩阵的左边缘和上边缘是“太平洋”，下边缘和右边缘是“大西洋”。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、遍历每个点，每个点来一次dfs，结果超时

class Solution {
public:/*** @param matrix: the given matrix* @return: The list of grid coordinates*/vector<vector<int>> globalans;vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {// write your code hereint row=matrix.size();int col=matrix[0].size();vector<vector<int>> matrixans(row,vector<int>(col));for(int i=0;i<row;i++){for(int j=0;j<col;j++){vector<vector<bool>> visited(row,vector<bool> (col));matrixans[i][j]=dfs(matrix,visited,matrixans,i,j);cout<< matrixans[i][j]<<" ";if(matrixans[i][j]==3){vector<int> temp;temp.push_back(i);temp.push_back(j);globalans.push_back(temp);}}cout<<endl;}return globalans;}int dfs(vector<vector<int>> &matrix,vector<vector<bool>> &visited,vector<vector<int>> &matrixans,int x,int y){int row=matrix.size();int col=matrix[0].size();int ans=0;visited[x][y]=true;if((x==0&&y==col-1)||(x==row-1&&y==0)){ans=3;return ans;}else if(x==0||y==0){ans=1;}else if(x==row-1||y==col-1){ans=2;}vector<vector<int>> move={{0,1},{1,0},{0,-1},{-1,0}};for(int i=0;i<4;i++){int pos_x=x+move[i][0];int pos_y=y+move[i][1];if(pos_x>=0&&pos_x<row&&pos_y>=0&&pos_y<col&&visited[pos_x][pos_y]==false&&matrix[x][y]>=matrix[pos_x][pos_y]){int temp;if(matrixans[pos_x][pos_y]!=0) temp=matrixans[pos_x][pos_y];else temp=dfs(matrix,visited,matrixans,pos_x,pos_y);if(ans==0) ans=temp;else if(temp!=0&&ans!=temp) ans=3; }}return ans;}
};

二、从边缘进行dfs，判断哪些点可达

class Solution {
public:/*** @param matrix: the given matrix* @return: The list of grid coordinates*/vector<vector<int>> globalans;int row;int col;vector<vector<int>> move={{0,1},{1,0},{-1,0},{0,-1}};vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {// write your code hererow=matrix.size();col=matrix[0].size();vector<vector<bool>> Pacific(row,vector<bool>(col));vector<vector<bool>> Atlantic(row,vector<bool>(col));for(int i=0;i<row;i++){dfs(matrix,Pacific,0,i,0);dfs(matrix,Atlantic,0,i,col-1);}for(int i=0;i<col;i++){dfs(matrix,Pacific,0,0,i);dfs(matrix,Atlantic,0,row-1,i);}for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(Pacific[i][j]&&Atlantic[i][j]){vector<int> temp;temp.push_back(i);temp.push_back(j);globalans.push_back(temp);}}}return globalans;}void dfs(vector<vector<int>> &matrix,vector<vector<bool>> &visited,int height,int x,int y){if(x<0||x>=row||y<0||y>=col||matrix[x][y]<height||visited[x][y]){return;}visited[x][y]=true;for(int i=0;i<4;i++){dfs(matrix,visited,matrix[x][y],x+move[i][0],y+move[i][1]);}}};

 

这篇关于LintCode 778 给定一个m×n的非负矩阵代表一个大洲，矩阵的每个单元格的值代表此处的地形高度，矩阵的左边缘和上边缘是“太平洋”，下边缘和右边缘是“大西洋”。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---