LeetCode 太平洋大西洋水流问题（深度优先搜索、广度优先搜索）

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：

输出坐标的顺序不重要
m 和 n 都小于150
1
2

示例：

给定下面的 5x5 矩阵:
  太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋
返回:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
1
2
3
4
5
6
7
8
9
10

思路分析：这道题是典型图的搜索问题，可以使用广度优先、深度优先搜索法。我们可以正向考虑从矩阵中的点去搜索太平洋、大西洋，也可以逆向考虑从太平洋、大西洋向高地搜索。我尝试了正向搜索，蛋式代码太长还超时。。。下面将介绍逆向搜索法。

第一步：从上边界的所有点向四周高地搜索，标记高地可达太平洋（水是从高地到达地处，逆向应该向高处）
第二步：从左边界的所有点向四周高地搜索，标记高地可达太平洋
第三步：从下边界的所有点向四周高地搜索，标记高地可达大西洋（水是从高地到达地处，逆向应该向高处）
第四步：从右边界的所有点向四周高地搜索，标记高地可达大西洋
第五步：遍历矩阵，判断点是否同时可达太平洋、大西洋
1
2
3
4
5

方法一：深度优先搜索法。

class Solution {
public:
	map<pair<int, int>, bool> pacificFlag;//标记[row,col]是否可达太平洋
	map<pair<int, int>, bool> atlanticFlag;//标记[row,col]是否可达大西洋
	vector<pair<int, int>> direction = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };//左、上、右、下是个方向
	//逆向搜索是否能够到达太平洋
	void dfsForPacific(vector<vector<int>>& matrix, int row, int col) {
		int rowSize = matrix.size(), colSize = matrix[0].size();
		//左、上、右、下是个方向进行寻找
		for (int index = 0; index < 4; ++index) {
			int nextRow = row + direction[index].first, nextCol = col + direction[index].second;
			//不能出边界、只能向高地搜索，且没有搜索过
			if (nextRow < 0 || nextRow >= rowSize || nextCol < 0 || nextCol >= colSize || matrix[row][col] > matrix[nextRow][nextCol] || pacificFlag.count({ nextRow, nextCol }) > 0) {
				continue;
			}
			pacificFlag[{nextRow, nextCol}] = true;//标记能够达到太平洋
			dfsForPacific(matrix, nextRow, nextCol);
		}
	}
	//逆向搜索是否能够到达大西洋
	void dfsForAtlantic(vector<vector<int>>& matrix, int row, int col) {
		int rowSize = matrix.size(), colSize = matrix[0].size();
		//左、上、右、下是个方向进行寻找
		for (int index = 0; index < 4; ++index) {
			int nextRow = row + direction[index].first, nextCol = col + direction[index].second;
			//不能出边界、只能向高地搜索，且没有搜索过
			if (nextRow < 0 || nextRow >= rowSize || nextCol < 0 || nextCol >= colSize || matrix[row][col] > matrix[nextRow][nextCol] || atlanticFlag.count({ nextRow, nextCol }) > 0) {
				continue;
			}
			atlanticFlag[{nextRow, nextCol}] = true;//标记能够达到太平洋
			dfsForAtlantic(matrix, nextRow, nextCol);
		}
	}
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		vector<pair<int, int>> result;
		int rowSize = matrix.size();
		if (rowSize == 0) {
			return result;
		}
		int colSize = matrix[0].size();
		if (colSize == 0) {
			return result;
		}
		for (int row = 0; row < rowSize; ++row) {
			//左边界，逆向搜索达到太平洋
			pacificFlag[{row, 0}] = true;
			dfsForPacific(matrix, row, 0);
			//右边界，逆向搜索达到大西洋
			atlanticFlag[{row, colSize - 1}] = true;
			dfsForAtlantic(matrix, row, colSize - 1);
		}
		for (int col = 0; col < colSize; ++col) {
			//上边界，逆向搜索达到太平洋
			pacificFlag[{0, col}] = true;
			dfsForPacific(matrix, 0, col);
			//下边界，逆向搜索达到大西洋
			atlanticFlag[{rowSize - 1, col}] = true;
			dfsForAtlantic(matrix, rowSize - 1, col);
		}
		//遍历矩阵
		for (int row = 0; row < rowSize; ++row) {
			for (int col = 0; col < colSize; ++col) {
				//是否能同时到达太平洋、大西洋
				if (pacificFlag[{row, col}] && atlanticFlag[{row, col}]) {
					result.push_back({ row, col });
				}
			}
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

==代码优化：==总感觉太平洋、大西洋分开进行搜索有些代码重复，下面对齐合并。

class Solution {
public:
	map<pair<int, int>, bool> pacificFlag;//标记[row,col]是否可达太平洋
	map<pair<int, int>, bool> atlanticFlag;//标记[row,col]是否可达大西洋
	vector<pair<int, int>> direction = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };//左、上、右、下是个方向
	//逆向搜索是否能够到达太平洋、大西洋，根据flag传入的是pacificFlag还是atlanticFlag进行区分
	void dfs(vector<vector<int>>& matrix, map<pair<int, int>, bool> &flag, int row, int col) {
		flag[{row, col}] = true;
		int rowSize = matrix.size(), colSize = matrix[0].size();
		//左、上、右、下是个方向进行寻找
		for (int index = 0; index < 4; ++index) {
			int nextRow = row + direction[index].first, nextCol = col + direction[index].second;
			//不能出边界、只能向高地搜索，且没有搜索过
			if (nextRow < 0 || nextRow >= rowSize || nextCol < 0 || nextCol >= colSize || matrix[row][col] > matrix[nextRow][nextCol] || flag.count({ nextRow, nextCol }) > 0) {
				continue;
			}
			flag[{nextRow, nextCol}] = true;//标记能够达到太平洋
			dfs(matrix, flag, nextRow, nextCol);
		}
	}
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		vector<pair<int, int>> result;
		int rowSize = matrix.size();
		if (rowSize == 0) {
			return result;
		}
		int colSize = matrix[0].size();
		if (colSize == 0) {
			return result;
		}
		for (int row = 0; row < rowSize; ++row) {
			dfs(matrix, pacificFlag, row, 0);//左边界，逆向搜索达到太平洋
			dfs(matrix, atlanticFlag, row, colSize - 1);//右边界，逆向搜索达到大西洋
		}
		for (int col = 0; col < colSize; ++col) {
			dfs(matrix, pacificFlag, 0, col);//上边界，逆向搜索达到太平洋
			dfs(matrix, atlanticFlag, rowSize - 1, col);//下边界，逆向搜索达到大西洋
		}
		//遍历矩阵
		for (int row = 0; row < rowSize; ++row) {
			for (int col = 0; col < colSize; ++col) {
				//是否能同时到达太平洋、大西洋
				if (pacificFlag[{row, col}] && atlanticFlag[{row, col}]) {
					result.push_back({ row, col });
				}
			}
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

方法二：广度优先搜索法。

class Solution {
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		vector<pair<int, int>> result;
		int rowSize = matrix.size();
		if (rowSize == 0) {
			return result;
		}
		int colSize = matrix[0].size();
		if (colSize == 0) {
			return result;
		}
		queue<pair<int, int>> pacificQue;//太平洋逆向广度优先搜索辅助队列
		queue<pair<int, int>> atlanticQue;//大西洋逆向广度优先搜索辅助队列
		map<pair<int, int>, bool> pacificFlag;//标记[row,col]是否可达太平洋
		map<pair<int, int>, bool> atlanticFlag;//标记[row,col]是否可达大西洋
		vector<pair<int, int>> direction = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };//左、上、右、下是个方向
		for (int row = 0; row < rowSize; ++row) {
			//左边界，逆向搜索达到太平洋
			pacificFlag[{row, 0}] = true;
			pacificQue.push({ row, 0 });
			//右边界，逆向搜索达到大西洋
			atlanticFlag[{row, colSize - 1}] = true;
			atlanticQue.push({ row, colSize - 1 });
		}
		for (int col = 0; col < colSize; ++col) {
			//上边界，逆向搜索达到太平洋
			pacificFlag[{0, col}] = true;
			pacificQue.push({ 0, col });
			//下边界，逆向搜索达到大西洋
			atlanticFlag[{rowSize - 1, col}] = true;
			atlanticQue.push({ rowSize - 1, col });
		}
		//逆向广度优先搜索到达太平洋的点
		while (!pacificQue.empty()) {
			//获取当前队头
			pair<int, int> front = pacificQue.front();
			pacificQue.pop();
			//左、上、右、下是个方向进行寻找
			for (int index = 0; index < 4; ++index) {
				int nextRow = front.first + direction[index].first, nextCol = front.second + direction[index].second;
				//不能出边界、只能向高地搜索，且没有搜索过
				if (nextRow < 0 || nextRow >= rowSize || nextCol < 0 || nextCol >= colSize || matrix[front.first][front.second] > matrix[nextRow][nextCol] || pacificFlag.count({ nextRow, nextCol }) > 0) {
					continue;
				}
				pacificFlag[{nextRow, nextCol}] = true;//标记能够达到太平洋
				pacificQue.push({ nextRow, nextCol });
			}
		}
		//逆向广度优先搜索到达大西洋的点
		while (!atlanticQue.empty()) {
			//获取当前队头
			pair<int, int> front = atlanticQue.front();
			atlanticQue.pop();
			//左、上、右、下是个方向进行寻找
			for (int index = 0; index < 4; ++index) {
				int nextRow = front.first + direction[index].first, nextCol = front.second + direction[index].second;
				//不能出边界、只能向高地搜索，且没有搜索过
				if (nextRow < 0 || nextRow >= rowSize || nextCol < 0 || nextCol >= colSize || matrix[front.first][front.second] > matrix[nextRow][nextCol] || atlanticFlag.count({ nextRow, nextCol }) > 0) {
					continue;
				}
				atlanticFlag[{nextRow, nextCol}] = true;//标记能够达到大西洋
				atlanticQue.push({ nextRow, nextCol });
			}
		}
		//遍历矩阵
		for (int row = 0; row < rowSize; ++row) {
			for (int col = 0; col < colSize; ++col) {
				//是否能同时到达太平洋、大西洋
				if (pacificFlag[{row, col}] && atlanticFlag[{row, col}]) {
					result.push_back({ row, col });
				}
			}
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77