代码随想录笔记-水流问题

内容:

凡是涉及到水的问题， 基本上都离不开正向和逆向两方面

这道题也是如此.

将左边界和上边界视为第一边界，将右边界和下边界视为第二边界

每个格子的数值代表该位置的高度，水流只能流向等高和比该位置低的地方。

因此 输入

5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1

会输出

0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1

 如图

(图源自代码随想录官网)

题解1. (正向)流出

设置一个visited ，标记该格子可以流过的地方，之后再去检查边界部分的visited的值

该想法很直观,但是会带来一个时间复杂度很高的问题.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
 
/**
 * @author hasno
 */
public class Main {
    static int[][] dir = {
  
  {1,0},{0,1},{-1,0},{0,-1}};
    //向下,向右,向上,向左
    public static void dfs(int[][] graph,int[][] visited,int x,int y) {
        if(visited[x][y] == 1) return;
        visited[x][y] = 1;
        for(int i = 0 ; i < 4 ; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if(nexty < 0 || nextx < 0 || nextx >= graph.length || nexty >= graph[0].length) {
                continue;
            }
            if(graph[x][y] < graph[nextx][nexty] ) {
                continue;
            }
            dfs(graph,visited,nextx,nexty);
        }
    }
    public static boolean isResult(int[][] graph , int x , int y) {
 
        int[][] visited = new int[graph.length][graph[0].length];
 
        dfs(graph,visited,x,y);
 
        boolean isFirst = false;
        boolean isSecond = false;
 
        for(int i = 0 ; i < graph.length ; i++) {
            if (visited[i][0] == 1) {
                isFirst = true;
                break;
            }
        }
        for(int i = 0 ; i < graph[0].length ; i++) {
            if (visited[0][i] == 1) {
                isFirst = true;
                break;
            }
        }
 
        for(int i = 0 ; i < graph.length ; i++) {
            if (visited[i][graph[0].length-1] == 1) {
                isSecond = true;
                break;
            }
        }
        for(int i = 0 ; i < graph[0].length ; i++) {
            if (visited[graph.length-1][i] == 1) {
                isSecond = true;
                break;
            }
        }
        return isFirst && isSecond;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //行数
        int n = scanner.nextInt();
        //列数
        int m = scanner.nextInt();
 
        int[][] graph = new int[n][m];
 
        for (int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }
 
        List> result = new ArrayList<>();
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
               if(isResult(graph,i,j)) {
                   result.add(Arrays.asList(i,j));
               }
            }
        }
        for (List pri : result) {
            System.out.println(pri.get(0) + " " + pri.get(1));
        }
 
    }
}

题解2. (逆向)逆流而上 

从边界开始往某一点去逆流而上。

检测条件: 必须要满足 本个比下一个小，才能标记下一个，否则无法标记

大体思路跟上面的区别不大，但是本质是以空间去换时间

记录两个边界逆流而上，看两个边界都能流到的点 即为满足条件的点

 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
 
/**
 * @author hasno
 */
public class Main {
    static int[][] dir = {
  
  {1,0},{0,1},{-1,0},{0,-1}};
    //向下,向右,向上,向左
    public static void dfs(int[][] graph,int[][] visited,int x,int y) {
        if(visited[x][y] == 1) {
            return;
        }
        visited[x][y] = 1;
        for(int i = 0 ; i < 4 ; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if(nexty < 0 || nextx < 0 || nextx >= graph.length || nexty >= graph[0].length) {
                continue;
            }
            if(graph[x][y] > graph[nextx][nexty] ) {
                continue;
            }
            dfs(graph,visited,nextx,nexty);
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //行数
        int n = scanner.nextInt();
        //列数
        int m = scanner.nextInt();
 
        int[][] graph = new int[n][m];
 
        for (int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }
        int[][] firstBroder = new int[n][m];
        int[][] secondBroder = new int[n][m];
        //左右
        for(int i = 0 ; i < n ; i++) {
            dfs(graph,firstBroder,i,0);
            dfs(graph,secondBroder,i,m-1);
        }
        for(int i = 0 ; i < m ; i++) {
            dfs(graph,firstBroder,0,i);
            dfs(graph,secondBroder,n-1,i);
        }
        List> result = new ArrayList<>();
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
               if(firstBroder[i][j] == 1 && secondBroder[i][j] == 1) {
                   result.add(Arrays.asList(i,j));
               }
            }
        }
        for (List pri : result) {
            System.out.println(pri.get(0) + " " + pri.get(1));
        }
 
    }
}

总结:

遇到水流问题，正向&逆向都必须要考虑！