搜索算法与二分答案结合课堂笔记

第一章 二分答案 + DFS（深度优先搜索）

1.1 问题模型

• 典型场景：在网格中寻找一条从第一行到最后一行的路径，使得路径上经过的最大数值尽可能小（即“最大值最小化”问题）。
• 核心思想：通过二分枚举“路径最大数值的上限”，用DFS验证是否存在满足条件的路径。

1.2 代码逐段解析

（1）全局变量与初始化

const int N = 1e3 + 10;
int t, n, m, a[N][N], vis[N][N], flag;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; // 方向数组：右、左、下、上

• a[N][N]：存储网格数值；vis[N][N]：标记点是否已访问（避免重复搜索）；flag：标记是否到达最后一行。
• 方向数组：通过dx[i]和dy[i]组合，统一实现四个方向的移动逻辑。

（2）DFS函数实现

void dfs(int x, int y, int limit){
    if(x == n){ // 到达最后一行，标记路径可行
        flag = 1;
        return ;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        // 边界判断 + 未访问 + 数值不超过当前二分限制
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0 && a[nx][ny] <= limit){
            vis[nx][ny] = 1; // 标记已访问
            dfs(nx, ny, limit); // 递归深入搜索
        }
    }
}

• 参数：(x,y)为当前坐标，limit为当前二分枚举的“最大数值上限”。
• 终止条件：x == n（到达最后一行），设置flag=1表示存在合法路径。
• 搜索逻辑：遍历四个方向，满足条件则标记并递归。

（3）check函数（验证二分答案）

bool check(int x){
    flag = 0;
    memset(vis, 0, sizeof vis); // 初始化访问数组为0
    vis[1][1] = 1; // 起点标记为已访问
    dfs(1, 1, x); // 从左上角(1,1)开始DFS
    return flag;
}

• 作用：检查当路径上最大数值不超过x时，能否从起点走到最后一行。
• memset注意：按字节初始化，适合初始化为0或-1（本题初始化为0）。

（4）主函数（二分答案框架）

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    int l = 0, r = 1000, ans = -1;
    while (l <= r){ // 二分边界：l <= r
        int mid = (l + r) / 2;
        if (check(mid) == 1){ // mid可行，尝试更小的答案
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1; // mid不可行，尝试更大的答案
    }
    cout << ans;
    return 0;
}

• 二分范围：l=0（最小可能值），r=1000（根据题目数值范围设定）。
• 二分逻辑：若mid可行，说明存在更优解（更小的最大值），故ans=mid且r=mid-1；若不可行，需增大mid，故l=mid+1。

1.3 注意事项

• 坐标范围：题目中网格从(1,1)到(n,m)，需注意边界判断（nx>=1 && nx<=n等）。
• vis数组初始化：每次check前必须用memset重置，否则上一次DFS的标记会影响结果。
• 二分边界细节：while(l <= r)保证所有可能值都被枚举，mid=(l+r)/2在整数溢出风险时可改为mid=l+(r-l)/2（本题范围小，无需担心）。

第二章 BFS（广度优先搜索）求最短路径

2.1 问题模型

• 典型场景：在网格图中，从起点S到终点T，只能走空地（非#），求最短路径长度（步数）。
• 核心思想：BFS按“层”搜索，第一次到达终点时的步数即为最短路径（BFS天然适合无权图最短路问题）。

2.2 代码逐段解析

（1）全局变量与结构体

const int N = 110;
int m, n, a[N][N], sx, sy, ex, ey, vis[N][N];
char c[N][N]; // 存储网格字符（S、T、#、.等）
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};

struct st{ // 结构体：存储每个点的坐标和步数
    int x, y, step;
};

• sx,sy：起点坐标；ex,ey：终点坐标；c[N][N]：存储网格地图。
• 结构体st：将(x,y)坐标与当前步数step绑定，方便入队存储。

（2）主函数与BFS框架

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> c[i][j];
            if(c[i][j] == 'S') sx = i, sy = j; // 记录起点
            if(c[i][j] == 'T') ex = i, ey = j; // 记录终点
        }
    }
    
    vis[sx][sy] = 1; // 起点标记为已访问
    queue<st> q;     // 定义队列，元素为结构体st
    q.push({sx, sy, 0}); // 起点入队，步数为0
    
    while(q.size() > 0){ // 队列不为空时循环
        st head = q.front(); // 取出队首元素
        q.pop();             // 队首出队
        
        for(int i = 0; i < 4; i++){
            int nx = head.x + dx[i];
            int ny = head.y + dy[i];
            int nstep = head.step + 1; // 下一步步数+1
            
            // 边界判断 + 未访问 + 不是障碍物
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0 && c[nx][ny] != '#'){
                vis[nx][ny] = 1; // 标记已访问（入队时标记，防止重复入队）
                q.push({nx, ny, nstep}); // 新点入队
                
                if(nx == ex && ny == ey){ // 到达终点，直接输出步数
                    cout << nstep;
                    return 0;
                }
            }
        }
    }
    return 0;
}

• 队列使用：queue<st>存储待搜索的点，BFS通过队列“先进先出”特性保证按层搜索。
• 入队标记：vis[nx][ny] = 1在入队时执行（而非出队时），避免同一个点被多次入队（关键优化！）。
• 终止条件：一旦到达终点(ex,ey)，立即输出nstep并结束程序（BFS第一次到达即为最短路径）。

2.3 注意事项

• 结构体初始化：q.push({sx, sy, 0})是C++11及以上的写法，若编译器不支持，可定义构造函数或单独赋值。
• 障碍物判断：c[nx][ny] != '#'确保只走合法路径（根据题目字符定义调整，如用.表示空地）。
• 队列空的情况：若队列空仍未到达终点，说明起点与终点不连通（本题默认有解，故未处理无解情况）。

第三章 DFS与BFS核心对比

第四章 核心技巧总结

1. 方向数组的使用

通过dx[]和dy[]统一处理四个方向的移动，避免重复写四组相似代码（可扩展至8方向，如对角线移动）。

2. 访问标记（vis数组）

• 作用：防止重复走同一个点，避免死循环或冗余搜索。
• 时机：DFS中“递归前标记”，BFS中“入队时标记”（关键！）。

3. 二分答案框架

• 适用：“最大值最小化”或“最小值最大化”问题（如本题中“路径最大数值的最小值”）。
• 关键：设计check(x)函数，验证“答案为x时是否可行”，再通过二分缩小范围。

4. BFS求最短路的核心

• 无权图中，BFS按层搜索的特性保证“第一次到达终点的步数最短”。
• 结构体绑定坐标与步数，方便队列存储状态。