Buckle practice - 20 rain II

20 Rainwater collection II

1. Problem description
To give you one m x n Matrix , The values are non negative integers , Represents the height of each cell in a two-dimensional height map , Please calculate the maximum volume of rainwater that the shape can receive .

Example ：

The following are given. 3x6 Height map :

[

[1,4,3,1,3,2],

[3,2,1,3,2,4],

[2,3,3,2,3,1]

]

return 4 .


The following codes can be used , Complete the trapRainWater function , Among them, formal parameters heightMap Is the above two-dimensional height map , Return the received rainwater volume .

#include

#include

#include

using namespace std;

class Solution {

public:

int trapRainWater(vector<vector<int> >& heightMap)

{

         // Fill in this function to complete the function   

}

};

int main()

{

int m, n,data;

vector<vector<int> > heights;

cin>>m>>n;

for(int i=0; i<m; i++)

{

    vector<int> row;

    for(int j=0; j<n; j++)

    {

        cin>>data;

        row.push_back(data);

    }

    heights.push_back(row);

}



int res=Solution().trapRainWater(heights);

cout<<res<<endl;

return 0;

}

2. Enter description :

First, enter the number of rows and columns of the height graph m and n

Then input m That's ok , Each row n Nonnegative integers , Express heightMap The element value of , Space off .

1 <= m, n <= 110

0 <= heightMap[i][j] <= 20000

3. The output shows that
Output an integer , Show the result .
4. Example
Input
3 6
1 4 3 1 3 2
3 2 1 3 2 4
2 3 3 2 3 1
Output
5. Code

#include<iostream>

#include<stack>
#include<queue>
#include<vector>

using namespace std;



class Solution {
    

public:

	int trapRainWater(vector<vector<int> >& heightMap)

	{
    
		// Barrel thought , Refer to the explanation of the question https://leetcode.cn/problems/trapping-rain-water-ii/solution/jie-yu-shui-ii-by-leetcode-solution-vlj3/
		//1. A special case 
		//heightMap.size() Represents the number of rows of the input matrix ,heightMap[0].size() Represents the number of columns ; If there are only two rows or two columns at most , Are the outermost squares around , It's impossible to receive rain 
		if (heightMap.size() <= 2 || heightMap[0].size() <= 2)
			return 0;
		//2. Definition 
		int m = heightMap.size();// Row number 
		int n = heightMap[0].size();// Number of columns 
		priority_queue<pair<int,int>, vector <pair<int,int>>, greater <pair<int,int>>>pq;// Priority queue 
		//3. Access tag initialization 
		// Reference resources https://blog.csdn.net/BShanj/article/details/113817328
		vector<vector<bool>> visited(m, vector<bool>(n, false));
		//4. Surrounding square mark processing 
		for (int i = 0; i < m; i++)
		{
    
			for (int j = 0; j < n; j++)
			{
    
				if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
				{
    
					visited[i][j] = true;
					// The outermost water connection water[i][j]=heightMap[i][j]
					pq.push({
     heightMap[i][j],i*n + j });// here second What is stored is the position of the box in column sorting , It is equivalent to starting from the first element of the first type , Back to S Type string into string 
				}
			}
		}
		//5. Processing center 
		// Suppose the index of the block is  (i,j), The height of the square is heightMap[i][j], The height of the block after receiving water is water[i][j]
		// square  (i,j)(i,j)  The height after water connection is ：water[i][j]=max(heightMap[i][j],min(water[i-1][j],water[i][j-1],water[i+1][j],water[i][j+1]))
		int res = 0;
		int direction[]={
     -1,0,1,0,-1 };// Left , On , Right , The next four directions 
		while (!pq.empty())// When is not empty 
		{
    
			pair<int, int> cur = pq.top();
			pq.pop();
			// Traverse the water level around this square 
			for (int k = 0; k < 4; k++)
			{
    
				int nx = cur.second / n + direction[k];// Be careful , here cur.second/n Represents the abscissa of the original square 
				int ny = cur.second%n + direction[k + 1];//cur.second%n Represents the ordinate of the original square 
				if (nx >= 0 && nx < m&&ny >= 0 && ny < n && !visited[nx][ny])// Here's a guarantee nx,ny All within the normal range 
				{
    
					// The height of the current box is higher than the surrounding box , The height of the water in the container depends on the lowest square in the outermost layer 
					if (heightMap[nx][ny] < cur.first)//cur.first It is the height of the square currently out of the queue heightMap[i][j]
						res += cur.first - heightMap[nx][ny];// square （i,j） The actual water connection is water[i][j]-heightMap[i][j]
					visited[nx][ny] = true;
					pq.push({
     max(heightMap[nx][ny], cur.first), nx * n + ny });
				}
			}
		}

		return res;

	}

};



int main()

{
    

	int m, n, data;

	vector<vector<int> > heights;

	cin >> m >> n;

	for (int i = 0; i < m; i++)

	{
    

		vector<int> row;

		for (int j = 0; j < n; j++)

		{
    

			cin >> data;

			row.push_back(data);

		}

		heights.push_back(row);

	}



	int res = Solution().trapRainWater(heights);

	cout << res << endl;

	return 0;

}