我们将土地表示为一个二维的高度数组,并使用以下模型,基于水流下坡的想法:
如果一个细胞的八个相邻细胞都有较高的海拔,我们称这个细胞为盆地;水汇集在盆地里。
否则,水会流向海拔最低的邻近细胞。
9 9 9 8 7 7 7
8 8 7 7 7
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 8 6
尺码8
9 9 9 8 8 8 8 8
8 8 8 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
突出显示的值形成最大尺寸盆地。
所以问题是
将地图划分为多个盆地。特别是,给定一个海拔地图,您的代码应该将地图划分为盆地,并输出最大盆地的大小。我们需要突出最大尺寸的盆地。
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]);
}
}
欢迎其他算法。
另外,在时间复杂度方面,有没有更好的算法?
这是我的工作代码。我也评论了我的每一个步骤,让你理解。如果你还能找到一些帮助,你可以去问。
算法
#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;
}
问题内容: 我正在尝试编写一种算法,用于在给定的子矩阵中查找子矩阵。为了解决这个问题,我编写了以下代码: 这段代码可以正常工作,但是我不确定这是问题的确切解决方案还是可以解决。请提供您的专家意见。提前致谢。 问题答案: 该算法对4×4矩阵和2×2子矩阵进行了硬编码。否则,它看起来像蛮力算法。 我会这样表示: 如果您想要更有效的方法,建议您将它们压扁,如下所示: 并在此序列中搜索以下模式: 使用标准
我有两个矩阵m1和m2: 乘法的结果是: 现在,我想让R给出相应乘法过程的最大值,而不是矩阵m3中的和积,例如: 我想得出以下矩阵: 如何做到这一点?
给定一个2维正整数数组,求和最大的HxW子矩形。矩形的总和是该矩形中所有元素的总和。 输入:具有正元素的二维数组NxN子矩形的HxW大小 输出:HxW大小的子矩阵,其元素的总和最大。 我已经使用蛮力方法解决了这个问题,但是,我现在正在寻找一个具有更好复杂性的更好的解决方案(我的蛮力法的复杂性是O(n6))。
我实现了c程序,可以找到矩阵的元素:行的最大元素,同时列的最小元素,或行的-min元素,同时列的最大元素。例如,我们有数据。包含以下内容的txt文件: 4 7 8 9 10 6 5 4 11 5 0 1 12 4 2 7 13- 其中4是n-矩阵大小(4x4),7和10是这些数字。 下面是代码: 问题:我想知道我的代码是不是“脏”代码?因为我总是渴望让一切变得如此困难,只要有可能让它变得容易。是否
我有一个大的NxN位数组,有K个1(其他都是0)。所有非零点的坐标都是已知的——换句话说,这个n×n数组可以表示为K对数组,每个数组包含一个非零点的x和y坐标。 给定一个HxW大小的子矩阵,我需要将其放在我的原始NxN数组上,使其覆盖大多数非零点。 输入:子矩阵的高度H和宽度W 输出:HxW子数组的x和y协弦,其内部有最多的协弦 之前也回答过类似的问题:2D矩阵中尺寸为HxW的最大子阵列,但在我的
(来自讲义参考)为了使高斯-塞德尔和雅可比方法收敛,有必要检查系数矩阵是否对角占优,即对角元素应该在其列中的所有元素中具有最大的值。如果它还不是对角占优,请使用旋转。对于对角占优的矩阵,应满足以下条件:(这也称为收敛) 是否有任何预定义的函数可以在maxima中使用以实现收敛,或者应该使用交换进行循环,以及应该使用什么约束?假设矩阵的大小为3x3,具有非零元素。 我已经看到了一些相关的问题,但答案