題意
思路
一開始想用雙向廣搜來做，
找他們相碰的點，
但是發現對其的理解還是不夠完全，
導致沒寫成功。
不過，
後來想清楚了，
之前的錯誤可能在於從邊界點進行BFS，
其訪問順序應該是找到下一個比當前那個要大的點，
但是我寫反了。
。
可以先對左邊的佇列進行BFS，
保存其visited，
再接著對右邊的佇列進行BFS，
當訪問到之前已經訪問過的結點時，
則加入到結果中。
實現// // #include "../PreLoad.h" /* Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 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 * * * * * * Atlantic Return: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix). */ class Solution { public: /** * 從邊界的點開始進行BFS，
找出交叉的點，
即為可以到達兩邊的點 * @param matrix * @return */ vector> pacificAtlantic(vector>& matrix) { vector> result; if (matrix.size == 0) { return result; } // 雙向BFS，
找重合點 queue> pa_queue; //太平洋 queue> at_queue; //大西洋 size_t row = matrix.size; size_t col = matrix[0].size; vector> layouts = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; auto state_bfs = [&](queue>& queue, vector>& visit) { while (!queue.empty) { pair content = queue.front; queue.pop; int height = content.first; int x = content.second / col; int y = content.second % col; for (auto temp : layouts) { int newx = temp[0] + x; int newy = temp[1] + y; // 因為是從邊界結點開始，
題目又要求某個點從高往低到兩個海洋，
所以邊界點訪問順序則為遞增 if (newx = row || newy = col || visit[newx][newy] || matrix[newx][newy] < height)="" {="" continue;="" }="" queue.push({matrix[newx][newy],="" newx="" *="" col="" +="" newy});="" visit[newx][newy]="1;" }="" }="" };="" vector=""> visited1(row, vector(col, 0)); vector> visited2(row, vector(col, 0)); // 第一行和第一列 for (int i = 0; i < col;="" i++)="" {="" pa_queue.push({matrix[0][i],="" i});="" visited1[0][i]="1;" at_queue.push({matrix[row-1][i],="" (row-1)="" *="" col="" +="" i});="" visited2[row-1][i]="1;" }="" for="" (int="" i="0;" i="">< row;="" i++)="" {="" pa_queue.push({matrix[i][0],="" i="" *="" col});="" visited1[i][0]="1;" at_queue.push({matrix[i][col-1],="" i="" *="" col="" +="" col-1});="" visited2[i][col-1]="1;" }="" state_bfs(pa_queue,="" visited1);="" state_bfs(at_queue,="" visited2);="" 交叉點則為可以到達兩邊的點="" for="" (int="" i="0;" i="">< row;="" i++)="" {="" for="" (int="" j="0;" j="">< col;="" j++)="" {="" if="" (visited1[i][j]="" &&="" visited2[i][j])="" {="" result.push_back({i,="" j});="" }="" }="" }="" return="" result;="" }="" vector=""> pacificAtlantic2(vector>& matrix) { vector> result; if (matrix.size == 0) { return result; } // 雙向BFS，
找重合點 queue> pa_queue; //太平洋 queue> at_queue; //大西洋 size_t row = matrix.size; size_t col = matrix[0].size; vector> layouts = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; auto state_bfs = [&](queue>& queue, vector>& visit, bool flag) { while (!queue.empty) { pair content = queue.front; queue.pop; int height = content.first; int x = content.second / col; int y = content.second % col; for (auto temp : layouts) { int newx = temp[0] + x; int newy = temp[1] + y; // 因為是從邊界結點開始，
題目又要求某個點從高往低到兩個海洋，
所以邊界點訪問順序則為遞增 if (newx = row || newy = col || matrix[newx][newy] < height)="" {="" continue;="" }="" if="" (flag)="" {="" if="" (visit[newx][newy]="" !="1)" {="" 已經被另外一個訪問過="" if="" (visit[newx][newy]="=" 2)="" {="" result.push_back({newx,="" newy});="" continue;="" }="" queue.push({matrix[newx][newy],="" newx="" *="" col="" +="" newy});="" visit[newx][newy]="1;" }="" }="" else="" {="" if="" (visit[newx][newy]="" !="2)" {="" 已經被另外一個訪問過="" if="" (visit[newx][newy]="=" 1)="" {="" result.push_back({newx,="" newy});="" continue;="" }="" queue.push({matrix[newx][newy],="" newx="" *="" col="" +="" newy});="" visit[newx][newy]="2;" }="" }="" }="" }="" };="" vector=""> visited1(row, vector(col, 0)); vector> visited2(row, vector(col, 0)); // 第一行和第一列 for (int i = 0; i < col;="" i++)="" {="" pa_queue.push({matrix[0][i],="" i});="" visited1[0][i]="1;" at_queue.push({matrix[row-1][i],="" (row-1)="" *="" col="" +="" i});="" visited2[row-1][i]="2;" }="" for="" (int="" i="0;" i="">< row;="" i++)="" {="" pa_queue.push({matrix[i][0],="" i="" *="" col});="" visited1[i][0]="1;" at_queue.push({matrix[i][col-1],="" i="" *="" col="" +="" col-1});="" visited2[i][col-1]="2;" }="" while="" (!pa_queue.empty="" ||="" !at_queue.empty)="" {="" if="" (!pa_queue.empty)="" {="" state_bfs(pa_queue,="" visited1,="" true);="" }="" if="" (!at_queue.empty)="" {="" state_bfs(at_queue,="" visited2,="" false);="" }="" }="" 交叉點則為可以到達兩邊的點="" for="" (int="" i="0;" i="">< row;="" i++)="" {="" for="" (int="" j="0;" j="">< col;="" j++)="" {="" if="" (visited1[i][j]="" &&="" visited2[i][j])="" {="" result.push_back({i,="" j});="" }="" }="" }="" return="" result;="" }="" void="" test="" {="" vector=""> matrix = { {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} }; vector> result = this->pacificAtlantic2(matrix); for (int i = 0; i < result.size;="" i++)="" {="" pair="" content="result[i];" cout="">
