问题:

这是一个面试问题。

一群农民有一些海拔数据，我们将帮助他们了解降雨如何流过他们的农田。

我们将土地表示为一个二维的高度数组，并根据水流下坡的想法使用以下模型:

如果一个单元格的八个相邻单元格都具有较高的海拔高度，我们称这个单元格为盆地；水聚集在盆中。

否则，水会流向海拔最低的相邻单元格。

直接或间接排入同一个汇的细胞被称为同一个盆地的一部分。

下面是几个例子:

输入:

1 1 2
1 1 7
3 6 9

尺寸 4

9 9 9 8 7 7
8 8 7 7 7 8
8 8 8 7 7 7
8 8 8 9 9 9
8 8 8 7 7 7
4 4 5 5 5 5
5 5 5 6 6 7
5 5 5 8 8 6

尺寸 8

9 9 9 8 8 8
8 8 8 7 7 7
7 7 7 7 7 7
8 8 8 8 9 9
5 5 5 5 6 3
5 5 5 3 3 3

9号

突出显示的值构成了最大尺寸的盆地。

所以问题是

将 map 划分为盆地。特别是，给定一张海拔图，您的代码应该将 map 划分为盆地并输出最大盆地的大小。 我们需要突出显示最大尺寸的盆地。

如果问题有这个假设

“如果一个单元格不是汇点，您可以假设它有一个唯一的最低邻居，并且这个邻居将低于该单元格”

然后我可以想到这个解决方案

    Each array element is a node in a graph. Construct the graph adding edges between the nodes:
  1 If node A is the smallest among all of its own neighbors, don't add an edge (it's a sink)
  2 There is an edge between two neighbors A and B iff A is the smallest of all neighbors of B.
  3 Finally traverse the graph using BFS or DFS and count the elements in the connected components.

到目前为止我已经实现了算法的第三部分

#include<iostream>
#include<vector>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int cv[1000]; // array stores number of nodes in each connected components
int main()
{
queue<int>q;
bool visited[100000];

int t,i,j,x,y,cvindex=0;
int n,e;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&e);
vector< vector<int> >G(n);
memset(visited,0,sizeof(visited));

for(i=0;i<e;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}

int ans=0;
for(i=0;i<n;i++)
{
if(!visited[i]) 
{
q.push(i);
visited[i]=1;
cv[cvindex]++;

while(!q.empty())
{
int p=q.front();
q.pop();
for(j=0;j<G[p].size();j++)
{
if(!visited[G[p][j]])
{
visited[G[p][j]]=1;
q.push(G[p][j]);
cv[cvindex]++;
}
}
}
ans++;
cvindex++;
}
}
printf("%d\n",ans);
sort(cv,cv+cvindex);
for(int zz=0;zz<cvindex;zz++)
printf("%d ",cv[zz]);
}
}   

时间复杂度O(n*m)

但是如何在没有假设的情况下解决上述问题呢？ 我想要几乎相似的方法，稍作修改。

欢迎使用其他算法。

而且在时间复杂度方面有没有更好的算法？

最佳答案

这是我的工作代码。为了您的理解，我还评论了我的每一步。如果您仍然找到一些帮助，您可以寻求帮助。

算法

1. 首先根据高度存储索引。
2. 然后从最小高度迭代到最大高度。
3. 如果还没有访问过当前索引，则将其设为盆地表面(可以收集水的地方)，并将所有高度大于此的邻居设为非盆地表面。
4. 重复第 3 步，直到访问完所有索引。
5. 然后在声明每个索引的状态之后。我们需要找到最大的盆地表面。我们可以使用 DFS 找到它。

时间复杂度:O(ROWS*COLUMNS)

#include<iostream>
#include<vector>
#include<string.h>
#include<climits>

#define BASIN 1
#define NOT_BASIN 2
#define NOT_DEFINED_YET 3

#define ROW 1000
#define COLUMN 1000
#define MAXIMUM_HEIGHT_POSSIBLE 1000

using namespace std;

int heights[ROW][COLUMN];  // It stores the height
int maximumBasin[ROW][COLUMN]; // It stores the state of each index, Total 3 states possible, ( BASIN, NOT_BASIN, NOT_DEFINED_YET )
bool alreadyVisited[ROW][COLUMN]; // True, if currect index visited, otherwise false.
vector< pair<int, int> > heightsCoordinates[MAXIMUM_HEIGHT_POSSIBLE]; // It stores all the indexs of given height.
int N, M, maxHeightPossible;

int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

bool isValidLocation(int x, int y) {
    if(x < 0 || x > M || y < 0 || y > N || alreadyVisited[x][y] == true) return false;
    return true;
}

void DFS_FOR_MARKING_WITH_GIVEN_VALUE(int value, int x, int y) {
    maximumBasin[x][y] = value;
    alreadyVisited[x][y] = true;
    for(int i = 0; i < 8; i++) if( isValidLocation(x + dx[i], y + dy[i]) && heights[x + dx[i]][y + dy[i]] >= heights[x][y] ) DFS_FOR_MARKING_WITH_GIVEN_VALUE(value, x + dx[i], y + dy[i]);
}

void DFS_FOR_COUNTING_BASINS_TOGETHER(int &cnt, int x, int y) {
    cnt++;
    alreadyVisited[x][y] = true;
    for(int i = 0; i < 8; i++) if( isValidLocation(x+dx[i], y+dy[i]) && maximumBasin[x + dx[i]][y + dy[i]] ==  BASIN ) DFS_FOR_COUNTING_BASINS_TOGETHER(cnt, x + dx[i], y + dy[i]);
}

void printBasin() {
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) cout << maximumBasin[i][j] << "  ";
        cout << endl;
    }
}

main() {

    cin >> M >> N >> maxHeightPossible;
    int x, y;
    int maximumCounts = INT_MIN;
    int cntTemp = 0;

    /**
     Take input and set NOT_DEFINED_YET for maximumBasin.
    **/
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
             cin >> heights[i][j];
             maximumBasin[i][j] = NOT_DEFINED_YET;
             heightsCoordinates[ heights[i][j] ].push_back(pair<int, int>(i, j));
        }
    }

    /**
    Iterate from smallest to largest height.
    If current index is  "NOT_DEFINED_YET" (means it is the candidate index where water can collect).  Water will come here from all neighbourhood whose height is greater than this.
    For that I call DFS_FOR_MARKING_WITH_GIVEN_VALUE function.
    **/
    for( int i = 0; i <= maxHeightPossible; i++ ){
        if(heightsCoordinates[i].size() == 0) continue;
        for(int j = 0; j < heightsCoordinates[i].size(); j++) {
            x = heightsCoordinates[i][j].first;
            y = heightsCoordinates[i][j].second;
            if( maximumBasin[x][y] == NOT_DEFINED_YET ) {
                maximumBasin[x][y] = BASIN;
                alreadyVisited[x][y] = true;
                for(int k = 0; k < 8; k++) {
                    if( isValidLocation( x + dx[k], y + dy[k] ) ) {
                        if ( heights[x + dx[k]][ y + dy[k]] > heights[x][y] ) {
                            DFS_FOR_MARKING_WITH_GIVEN_VALUE(NOT_BASIN, x + dx[k], y + dy[k]);
                        }
                    }
                }
            }
            else {
                // If  it is set by BASIN or NOT_BASIN, Shows already processed before.
            }
        }
    }

    //printBasin();

    memset(alreadyVisited, 0, sizeof(alreadyVisited));

    /**
        It simply counts basins which are together.
    **/
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            if( alreadyVisited[i][j] == false && maximumBasin[i][j] == BASIN) {
                DFS_FOR_COUNTING_BASINS_TOGETHER(cntTemp, i, j);
                //cout << cntTemp << endl;
                if(cntTemp > maximumCounts ) maximumCounts = cntTemp;
                cntTemp = 0;
            }
        }
    }

    /**
        This is our final Answer.
    **/
    cout << maximumCounts << endl;
    return 0;
}

关于c++ - 在给定矩阵中找到最大的盆地大小，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24336686/