蓝桥杯算法实战指南：递推、递归、BFS 与 DFS 详解

卒只能向下或向右移动，因此到达点 (i, j) 的路径数等于上方点与左方点路径数之和。 关系式：rd[i][j] = rd[i-1][j] + rd[i][j-1]

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(vis[i][j]==1)continue; 
        rd[i][j]=rd[i-1][j]+rd[i][j-1]; 
    } 
}

完整代码如下。注意数据范围可能溢出，需使用 long long。

#include<bits/stdc++.h> 
using namespace std; 
#define int long long 
int mx[] = {-1,-1,-2,-2,1,1,2,2}; 
int my[] = {-2,2,-1,1,-2,2,-1,1}; 
int vis[110][110]={0}; 
int rd[110][110]={0}; 
signed main(){ 
    int n,m,cx,cy; 
    cin>>n>>m>>cx>>cy; 
    vis[cx][cy]=1; 
    for(int i=0;i<=7;i++){
        int nx=cx+mx[i]; 
        int ny=cy+my[i]; 
        if(nx<0 || ny<0 || nx>n || ny>m)continue; 
        vis[nx][ny]=1; 
    } 
    rd[0][0]=1; 
    for(int i=1;i<=n;i++){
        rd[i][0]=rd[i-1][0]; 
        if(vis[i][0]==1)rd[i][0]=0; 
    } 
    for(int i=1;i<=m;i++){
        rd[0][i]=rd[0][i-1]; 
        if(vis[0][i]==1)rd[0][i]=0; 
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j]==1)continue; 
            rd[i][j]=rd[i-1][j]+rd[i][j-1]; 
        } 
    } 
    cout<<rd[n][m]<<endl; 
    return 0; 
}

核心要点： 递推有两要素：边界条件和关系式。只要正确推出这两个要素，再从已知推未知，就可以轻松解决递推问题。

递归

经典引入

递归算法是直接或间接调用自身函数，通过循环回溯解决小问题，最后得出大问题的答案。核心是找到终止条件，否则会导致无限循环。

以斐波那契数列为例，公式为 f(n) = f(n-1)+f(n-2)。在函数中，当前第 n 位函数调用前两位，直到最底层返回结果。

int fb(int x){ 
    if(x==1 || x==2)return 1; 
    return fb(x-1)+fb(x-2); 
}

完整代码示例：

#include<bits/stdc++.h> 
using namespace std; 
int fb(int x){ 
    if(x==1 || x==2)return 1; 
    return fb(x-1)+fb(x-2); 
} 
int main(){ 
    int n; 
    cin>>n; 
    while(n--){ 
        int num; 
        cin>>num; 
        cout<<fb(num)<<endl; 
    } 
}

深入理解

结合正则表达式最长字符串匹配问题。规则如下：

• ( ) 及内容视为一组。
• | 为分界线，两边长度互不干扰，取最大值。
• x 为普通字符。

例如 ((xx|xxx)x|(x|xx))xx，先拆分组，计算每组最大长度，再累加普通字符。

核心逻辑是不断找组，根据符号判断。由于代码较完整，直接展示带注释的解法。

#include<bits/stdc++.h> 
using namespace std; 
int i=0; 
string s; 
int Longest(){ 
    int m_cnt=0; 
    int cnt=0; 
    while(i < s.size()){
        if(s[i] == '('){ 
            i++; 
            int n = Longest(); 
            cnt += n; 
        } else if(s[i] == 'x'){ 
            cnt++; 
            i++; 
        } else if(s[i] == '|'){ 
            m_cnt = max(m_cnt,cnt); 
            cnt=0; 
            i++; 
        } else { 
            i++; 
            break; 
        } 
    } 
    return max(cnt,m_cnt);
} 
int main(){ 
    cin>>s; 
    cout<<Longest(); 
}

核心要点： 递归最重要的一步是找到终止条件。找到式子间的关系，再循环调用即可解决问题。

BFS 广度优先搜索

基础模板

BFS 是一种图的遍历算法，从浅到深，宽度遍历。从一个节点开始，找它的邻居，再找邻居的邻居。

实现方式主要有两种：邻接矩阵和邻接表。邻接矩阵结构简单但空间复杂度高；邻接表适合数据量大的情况。

邻接矩阵实现

适用于无向图，n 个点，m 条边。

#include<bits/stdc++.h> 
using namespace std; 
int g[105][105]; 
int vis[105]; 
int n,m; 
void bfs(int start){ 
    queue<int> q; 
    q.push(start); 
    vis[start] = 1; 
    while(!q.empty()){ 
        int cur = q.front(); 
        q.pop(); 
        for(int i=1;i<=n;i++){ 
            if(g[cur][i] == 1 && vis[i] == 0){ 
                vis[i] = 1; 
                q.push(i); 
            } 
        } 
    } 
}
int main(){ 
    cin >> n >> m; 
    for(int i=1;i<=m;i++){ 
        int u,v; 
        cin >> u >> v; 
        g[u][v] = 1; 
        g[v][u] = 1; 
    } 
    bfs(1); 
    return 0; 
}

邻接表实现

#include<bits/stdc++.h> 
using namespace std; 
vector<int> adj[105]; 
int vis[105]; 
int n,m; 
void bfs(int start){ 
    queue<int> q; 
    q.push(start); 
    vis[start] = 1; 
    while(!q.empty()){ 
        int cur = q.front(); 
        q.pop(); 
        for(int i=0;i<adj[cur].size();i++){ 
            int nxt = adj[cur][i]; 
            if(vis[nxt] == 0){ 
                vis[nxt] = 1; 
                q.push(nxt); 
            } 
        } 
    } 
}
int main(){ 
    cin >> n >> m; 
    for(int i=1;i<=m;i++){ 
        int u,v; 
        cin >> u >> v; 
        adj[u].push_back(v); 
        adj[v].push_back(u); 
    } 
    bfs(1); 
    return 0; 
}

BFS 最短路问题

在无向图中求两点间最短路径。BFS 第一次走到某个点时，即为最短路径。

需要记录步数，结构体存储节点 ID 和步数。

#include<bits/stdc++.h> 
using namespace std; 
vector<int> adj[105]; 
int vis[105]; 
int n,m; 
int a,b; 
struct node{ 
    int id; 
    int step; 
}; 
void bfs(int start){ 
    queue<node> q; 
    node tmp; 
    tmp.id = start; 
    tmp.step = 0; 
    q.push(tmp); 
    vis[start] = 1; 
    while(!q.empty()){ 
        int curId = q.front().id; 
        int curStep = q.front().step; 
        q.pop(); 
        for(int i=0;i<adj[curId].size();i++){ 
            node nxt; 
            nxt.id = adj[curId][i]; 
            nxt.step = curStep + 1; 
            if(nxt.id == b){ 
                cout << nxt.step << endl; 
                return; 
            } 
            if(vis[nxt.id] == 0){ 
                vis[nxt.id] = 1; 
                q.push(nxt); 
            } 
        } 
    } 
}
int main(){ 
    cin >> n >> m; 
    for(int i=1;i<=m;i++){ 
        int u,v; 
        cin >> u >> v; 
        adj[u].push_back(v); 
        adj[v].push_back(u); 
    } 
    cin >> a >> b; 
    bfs(a); 
    return 0; 
}

DFS 深度优先搜索

基础模板

DFS 算法纵向搜索，尽可能深地探入，直到无法搜索，然后回溯。核心思想是递归调用。

同样提供邻接矩阵和邻接表两种实现。

邻接矩阵实现

#include<bits/stdc++.h> 
using namespace std; 
const int N=1000; 
int a[N][N]; 
int vis[N]; 
void dfs(int cur){ 
    vis[cur]=1; 
    for(int i=1;i<=n;i++){ 
        if(a[cur][i]==1 && vis[i]==0){ 
            dfs(i); 
        } 
    } 
}
int main(){ 
    cin >> n >> m; 
    for(int i=1;i<=m;i++){ 
        int u,v; 
        cin >> u >> v; 
        a[u][v]=1; 
        a[v][u]=1; 
    } 
    dfs(1); 
    return 0; 
}

邻接表实现

#include<bits/stdc++.h> 
using namespace std; 
const int N=1000; 
vector<int>a[N]; 
int vis[N]; 
void dfs(int cur){ 
    vis[cur]=1; 
    for(int i=1<a[cur].size();i++){ 
        int nxt=a[cur][i]; 
        if(vis[nxt]==0){ 
            dfs(i); 
        } 
    } 
}
int main(){ 
    cin >> n >> m; 
    for(int i=1;i<=m;i++){ 
        int u,v; 
        cin >> u >> v; 
        a[u].push_back(v); 
        a[v].push_back(u); 
    } 
    dfs(1); 
    return 0; 
}

迷宫问题

DFS 版

迷宫问题通常要求判断能否从起点走到终点。支持上下左右移动，不能穿墙。

多组测试数据时，建议使用邻接矩阵而非邻接表，因为输入新数据时旧数据会被清空，避免清理动态数组的麻烦。

需要方向数组控制移动：nx[]={-1,0,0,1}, ny[]={0,-1,1,0}。

#include<bits/stdc++.h> 
using namespace std; 
int n; 
char maze[110][110]; 
int vis[110][110]; 
int xA,yA,xB,yB; 
int nx[]={-1,0,0,1}; 
int ny[]={0,-1,1,0}; 
bool judge(int x,int y){ 
    if(x<0 || y<0 || x>=n || y>=n)return false; 
    if(maze[x][y]=='.')return true; 
    else return false; 
} 
bool dfs(int sx,int sy){ 
    int cur_x=sx; 
    int cur_y=sy; 
    vis[cur_x][cur_y]=1; 
    if(cur_x == xB && cur_y == yB)return true; 
    for(int i=0;i<4;i++){ 
        int nxt_x=cur_x+nx[i]; 
        int nxt_y=cur_y+ny[i]; 
        if(judge(nxt_x,nxt_y) && vis[nxt_x][nxt_y]==0){ 
            if(dfs(nxt_x,nxt_y))return true; 
        } 
    } 
    return false; 
}
int main(){ 
    int k; 
    cin>>k; 
    while(k--){ 
        cin>>n; 
        for(int i=0;i<n;i++){ 
            for(int j=0;j<n;j++){ 
                char c; 
                cin>>c; 
                maze[i][j]=c; 
                vis[i][j]=0; 
            } 
        } 
        cin>>xA>>yA>>xB>>yB; 
        bool ans=dfs(xA,yA); 
        if(ans)cout<<"YES"<<endl; 
        else cout<<"NO"<<endl; 
    } 
    return 0; 
}

BFS 版

BFS 版本用于求解迷宫最短路。DFS 需要罗列所有路径，复杂度指数级；BFS 第一次走到终点即为最短路，复杂度 O(n)。

基本思路相同，主要区别在于使用队列存储状态。

#include<iostream> 
#include<queue> 
using namespace std; 
int n; 
char maze[110][110]; 
int vis[110][110]; 
int xA, yA, xB, yB; 
int nx[] = {-1, 0, 0, 1}; 
int ny[] = {0, -1, 1, 0}; 
bool judge(int x, int y) { 
    if (x < 0 || y < 0 || x >= n || y >= n) return false; 
    if (maze[x][y] == '.') return true; 
    else return false; 
} 
void bfs(int sx, int sy) { 
    queue<pair<int, int>> q; 
    q.push({sx, sy}); 
    vis[sx][sy] = 1; 
    while (!q.empty()) { 
        int cur_x = q.front().first; 
        int cur_y = q.front().second; 
        q.pop(); 
        if (cur_x == xB && cur_y == yB) { 
            return; 
        } 
        for (int i = 0; i < 4; i++) { 
            int nxt_x = cur_x + nx[i]; 
            int nxt_y = cur_y + ny[i]; 
            if (judge(nxt_x, nxt_y) && vis[nxt_x][nxt_y] == 0) { 
                q.push({nxt_x, nxt_y}); 
                vis[nxt_x][nxt_y] = 1; 
            } 
        } 
    } 
}
int main() { 
    int k; 
    cin >> k; 
    while (k--) { 
        cin >> n; 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) { 
                char c; 
                cin >> c; 
                maze[i][j] = c; 
                vis[i][j] = 0; 
            } 
        } 
        cin >> xA >> yA >> xB >> yB; 
        bfs(xA, yA); 
        if (vis[xB][yB]) cout << "YES" << endl; 
        else cout << "NO" << endl; 
    } 
    return 0; 
}

以上就是迷宫问题的基本思路和解法，希望带给大家一点启发。