第十四届第三期蓝桥模拟赛深搜题解

1. 最大连通

这道可以说是深搜基础的题，在数据范围内，我们可以爆搜，对每个点依次，求其连通量的最大值，但为了可以降低复杂度，本题我们也可以使用记忆化搜索，记忆化搜索应该是我们进行搜索时，必定应该考虑的一步。

本题的 记忆化搜索代码如下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class 最大连通 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static char ch [][] = new char [30][60];
    static int b[][] = new int [30][60];
    static boolean st [][] = new boolean [30][60];
    static int [] dx = {1,0,-1,0};
    static int [] dy = {0,1,0,-1};
    public static void main(String agrs[]) throws IOException {
        for(int i=0;i<30;i++) {
            ch[i]=br.readLine().toCharArray();
        }
        int ans = 0;
        for(int i=0;i<30;i++) {
            for(int j=0;j<60;j++) {
                if(ch[i][j]=='0')continue;
                ans = Math.max(ans, dfs(i,j));
            }
        }
        System.out.println(ans);
    }
    static int dfs(int x,int y) {
        if(b[x][y]!=0)return b[x][y];
        b[x][y] = 1;
        st[x][y] = true;
        for(int i=0;i<4;i++) {
            int tx = x+dx[i];
            int ty = y+dy[i];
            if(tx>=0&&tx<30&&ty>=0&&ty<60&&ch[tx][ty]=='1'&&st[tx][ty]==false) {//控制边界，已被标记过的无需重复遍历
                st[tx][ty] = true;
                b[x][y] += dfs(tx,ty);//将子节点的值累加到父节点
            }
        }
        return b[x][y];
    }
}

b[][]依次记录以某个点为父节点，依次遍历有多少子节点，因此只有该连通块的第一个点作为父节点遍历子节点时得到的值为最大值，其余结点依次比其小1；在遍历时，如果遇到该点在b[][]中有记录，则无需遍历，因此，通过这种搜索，图中的每个点将只会遍历一次，无需重重复遍历，并且在最后我们可以使用

ans = Math.max(ans, dfs(i,j));

找出连通块中数量最大的值

2. 滑行

同理 ，本题的数据范围为100*100，因此所有点数为10000，如果对每个点依次遍历其所有子节点，复杂度为10000*10000=1e8，会超时，因此本题必须使用记忆化搜索，对每个点仅遍历一次，那么复杂度将为10000。依然采用b[][]作为记忆数组。详细代码如下：

 
import java.util.Scanner;
 
public class 滑行 {
    static int n,m;
    static int [] dx = {1,0,-1,0};
    static int [] dy = {0,-1,0,1};
    static int [][] h = new int [110][110];
    static int [][] b = new int [110][110];
    public static void main(String agrs[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                h[i][j] = sc.nextInt();
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                ans = Math.max(ans,dfs(i,j));
            }
        }
        System.out.println(ans);
    }
    static int dfs(int x,int y) {
        if(b[x][y]!=0)return b[x][y];
        b[x][y] = 1;
        for(int i=0;i<4;i++) {
            int tx = x+dx[i];
            int ty = y+dy[i];
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&h[tx][ty]<h[x][y]) {
                b[x][y]=Math.max(b[x][y], dfs(tx,ty)+1);
            }
        }
        return b[x][y];
    }
}

其中最关键的代码如下：

 b[x][y]=Math.max(b[x][y], dfs(tx,ty)+1);//对各个子节点进行比较，选择滑行距离最大的子结点