水流问题[图搜索优化]
学习要点
- 图的搜索优化
题目链接
103. 水流问题
题目描述
解法：时间超限。但是解法是正确的
#include #include #include #include using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};bool first_line = false;bool second_kine = false;void dfs(vector<vector> &grid,vector<vector>& visits, int x, int y) { visits[x][y] = true; // 要注意环的问题 if(x == 0 || y == 0) { first_line = true; } if(x == grid.size() - 1 || y == grid[0].size() - 1) { second_kine = true; } if(first_line == true && second_kine == true) { return; } // queue<pair> que_equ; for (int i = 0; i < 4; i++) { int next_x = x + dir[i][0]; int next_y = y + dir[i][1]; // 越界 if (next_x < 0 || next_y = grid.size() || next_y >= grid[0].size()) { continue; } // 不可走 if(grid[x][y] = grid[next_x][next_y]) { dfs(grid,visits,next_x,next_y); } }}int main() { int n, m; cin >> n >> m; vector<vector> grid(n, vector(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j > grid[i][j]; // cout << grid[i][j]; } } vector<vector> visits(n,vector(m,false)); vector<vector> tmp_visits(n,vector(m,false)); vector<pair> ret_v; for(int i = 0;i<n;i++) { for(int j = 0; j<m; j++) { // 回位 visits = tmp_visits; first_line = false; second_kine = false; dfs(grid,visits,i,j); if(first_line == true && second_kine == true) { ret_v.push_back({i,j}); } } } for(auto& i_pair: ret_v) { cout << i_pair.first << \' \' << i_pair.second << endl; }}解法：时间还是超限，快一点了
#include #include #include #include using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};bool first_line = false;bool second_kine = false;void dfs(vector<vector> &grid,vector<vector>& visits, vector<vector>& mem_v, int x, int y) { if(mem_v[x][y] == true) { first_line = true;second_kine = true; return; } visits[x][y] = true; // 要注意环的问题 if(x == 0 || y == 0) { first_line = true; } if(x == grid.size() - 1 || y == grid[0].size() - 1) { second_kine = true; } if(first_line == true && second_kine == true) { return; } // queue<pair> que_equ; for (int i = 0; i < 4; i++) { int next_x = x + dir[i][0]; int next_y = y + dir[i][1]; // 越界 if (next_x < 0 || next_y = grid.size() || next_y >= grid[0].size()) { continue; } // 不可走 if(grid[x][y] = grid[next_x][next_y]) { dfs(grid,visits,mem_v,next_x,next_y); if(first_line == true && second_kine == true) { return; } } }}int main() { int n, m; cin >> n >> m; vector<vector> grid(n, vector(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j > grid[i][j]; // cout << grid[i][j]; } } vector<vector> mem_v(n,vector(m,false)); vector<vector> visits(n,vector(m,false)); vector<vector> tmp_visits(n,vector(m,false)); vector<pair> ret_v; for(int i = 0;i<n;i++) { for(int j = 0; j0 && j>0 && grid[i][j] >= grid[i-1][j] && mem_v[i-1][j] == true) { ret_v.push_back({i,j}); mem_v[i][j] = true; continue; } if(i>0 && j>0 && grid[i][j] >= grid[i][j-1] && mem_v[i][j-1] == true) { ret_v.push_back({i,j}); mem_v[i][j] = true; continue; } // 回位 visits = tmp_visits; first_line = false; second_kine = false; dfs(grid,visits,mem_v,i,j); if(first_line == true && second_kine == true) { ret_v.push_back({i,j}); mem_v[i][j] = true; } } } for(auto& i_pair: ret_v) { cout << i_pair.first << \' \' << i_pair.second << endl; }}解法：逆向
#include #include using namespace std;int n, m;int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};void dfs(vector<vector>& grid,vector<vector>& visits,int x, int y){ visits[x][y] = true; for(int i = 0;i<4;i++) { int next_x = x + dir[i][0]; int next_y = y + dir[i][1]; if(next_x < 0 || next_y = grid.size() || next_y >= grid[0].size()) { continue; } if(grid[x][y] > grid[next_x][next_y]) { continue; } if(visits[next_x][next_y] == true) { continue; } dfs(grid,visits,next_x,next_y); }}int main() { cin >> n >> m; vector<vector> grid(n, vector(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j > grid[i][j]; } } vector<vector> firstBorder(n, vector(m, false)); vector<vector> secondBorder(n, vector(m, false)); for(int i = 0; i<n; i++) { if(firstBorder[i][0] == true) continue; dfs(grid,firstBorder,i,0); } for(int i = 0; i<m;i++) { if(firstBorder[0][i] == true) continue; dfs(grid,firstBorder,0,i); } for(int i = 0; i<m; i++) { if(secondBorder[n-1][i] == true) continue; dfs(grid,secondBorder,n-1,i); } for(int i = 0; i<n; i++) { if(secondBorder[i][m-1] == true) continue; dfs(grid,secondBorder,i,m-1); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果 if (firstBorder[i][j] && secondBorder[i][j]) cout << i << \" \" << j << endl;; } }}
