水流问题[图搜索优化]

学习要点

1. 图的搜索优化

题目链接

        103. 水流问题

题目描述

解法：时间超限。但是解法是正确的

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
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<int>> &grid,vector<vector<bool>>& 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<int,int>> 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 < 0 || next_x >= grid.size() ||
        next_y >= grid[0].size())
    {
        continue;
    }
    // 不可走
    if(grid[x][y] < grid[next_x][next_y])
    {
        continue;
    }
    // 已经走过此路，也许还未走完
    if(visits[next_x][next_y])
    {
        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<int>> grid(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> grid[i][j];
    //   cout << grid[i][j];
    }
  }

  vector<vector<bool>> visits(n,vector<bool>(m,false));
  vector<vector<bool>> tmp_visits(n,vector<bool>(m,false));
  vector<pair<int,int>> 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 <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
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<int>> &grid,vector<vector<bool>>& visits, vector<vector<bool>>& 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<int,int>> 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 < 0 || next_x >= grid.size() ||
        next_y >= grid[0].size())
    {
        continue;
    }
    // 不可走
    if(grid[x][y] < grid[next_x][next_y])
    {
        continue;
    }
    // 已经走过此路，也许还未走完
    if(visits[next_x][next_y])
    {
        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<int>> grid(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> grid[i][j];
    //   cout << grid[i][j];
    }
  }
    vector<vector<bool>> mem_v(n,vector<bool>(m,false));
  vector<vector<bool>> visits(n,vector<bool>(m,false));
  vector<vector<bool>> tmp_visits(n,vector<bool>(m,false));
  vector<pair<int,int>> ret_v;
  for(int i = 0;i<n;i++)
  {
    for(int j = 0; j<m; j++)
    {
        if(i>0 && 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 <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};

void dfs(vector<vector<int>>& grid,vector<vector<bool>>& 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 < 0 || next_x >= 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<int>> grid(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> firstBorder(n, vector<bool>(m, false));
    vector<vector<bool>> secondBorder(n, vector<bool>(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;;
        }
    }

}