2025-03-24[DFS]联通性_回溯法

[DFS]联通性_回溯法

DFS解决连通性问题

• DFS不能保证搜索路径最短
• 但是实现代码相对简单

回溯法暴搜

• 回溯法可以暴力枚举一些问题
• 一些状态作为dfs函数的参数
• 在终点更新某些值

例题

迷宫

// http://ybt.ssoier.cn:8088/problem_show.php?pid=1215

/**
 * 联通性问题的DFS解决
 * DFS不能保证搜索路径最短
 * 但是实现代码相对简单
*/

#include<bits/stdc++.h>
using namespace std;

const int N=110;

int xa, ya, xb, yb;
int n;
char g[N][N];
bool st[N][N];

int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};

bool dfs(int x, int y){
    if(x==xb && y==yb) return true;
    
    st[x][y]=true;

    // 这块写法类似BFS
    for(int i=0;i<4;i++){
        int a=x+dx[i], b=y+dy[i];

        if(a<0 || a>=n || b<0 || b>=n) continue;
        if(st[a][b]) continue;
        if(g[a][b]=='#') continue;

        if(dfs(a, b)) return true;
    }

    return false;
}

void work(){
    int k;
    cin>>k;

    while(k--){
        cin>>n;

        for(int i=0;i<n;i++)
            cin>>g[i];

        cin>>xa>>ya>>xb>>yb;

        memset(st, 0, sizeof st);
        cout<<(dfs(xa, ya)?"YES":"NO")<<endl;
    }
}

int main(){
    work();
    return 0;
}

红与黑

// http://ybt.ssoier.cn:8088/problem_show.php?pid=1216

/**
 * 连通性问题DFS
*/

#include<bits/stdc++.h>
using namespace std;

const int N=30;

int n, m;
int sx, sy;
char g[N][N];
bool st[N][N];

int dx[4]={0, 1, 0, -1};
int dy[4]={1, 0, -1, 0};

int dfs(int x, int y){
    int cnt=1;
    st[x][y]=true;

    for(int i=0;i<4;i++){
        int a=x+dx[i], b=y+dy[i];

        if(a<0 || a>=n || b<0 || b>=m) continue;
        if(st[a][b]) continue;
        if(g[a][b]=='#') continue;

        cnt+=dfs(a, b);
    }

    return cnt;
}

void work(){
    while(cin>>m>>n, m || n){
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                cin>>g[i][j];
                if(g[i][j]=='@') sx=i, sy=j;
            }
                
        memset(st, 0, sizeof st);
        cout<<dfs(sx, sy)<<endl;
    }
}

int main(){
    work();
    return 0;
}

马走日

// http://ybt.ssoier.cn:8088/problem_show.php?pid=1219

/**
 * 回溯法解决问题，参数cnt记录当前已访问了几个结点
*/

#include<bits/stdc++.h>
using namespace std;

const int N=15;

int n, m, sx, sy;
bool st[N][N];
int ans;

int dx[8]={1, 1, 2, 2, -1, -1, -2, -2};
int dy[8]={2, -2, 1, -1, 2, -2, 1, -1};

void dfs(int x, int y, int cnt){

    if(cnt==n*m){
        ans++;
        return ;
    } 

    st[x][y]=true;

    for(int i=0;i<8;i++){
        int a=x+dx[i], b=y+dy[i];

        if(a<0 || a>=n || b<0 || b>=m) continue;
        if(st[a][b]) continue;

        dfs(a, b, cnt+1);
    }

    st[x][y]=false;// 恢复现场
}

void work(){
    int T;
    cin>>T;

    while(T--){
        cin>>n>>m>>sx>>sy;

        memset(st, 0, sizeof st);
        dfs(sx, sy, 1);

        cout<<ans<<endl;

        ans=0;
    }
}

int main(){
    work();
    return 0;
}

单词接龙

// http://ybt.ssoier.cn:8088/problem_show.php?pid=1220

#include<bits/stdc++.h>
using namespace std;

const int N=25;

int n;
string word[N];
int g[N][N];// 单词相接最短长度
int st[N];
int ans;

void dfs(int u, int dragon){
    ans=max(ans, dragon);

    st[u]++;

    for(int i=0;i<n;i++){
        if(st[i]>=2) continue;
        if(g[u][i]==0) continue;

        dfs(i, dragon-g[u][i]+word[i].size());
    }

    st[u]--;
}

void work(){
    cin>>n;

    for(int i=0;i<n;i++) cin>>word[i];

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            string a=word[i], b=word[j];
            for(int k=1;k<=min(a.size(), b.size());k++)
                if(a.substr(a.size()-k, k)==b.substr(0, k)){
                    g[i][j]=k;
                    break;
                }
        }

    char sta;
    cin>>sta;

    for(int i=0;i<n;i++)
        if(word[i][0]==sta)
            dfs(i, word[i].size());

    cout<<ans<<endl;
}

int main(){
    work();
    return 0;
}

分成互质组

// http://ybt.ssoier.cn:8088/problem_show.php?pid=1221

#include<bits/stdc++.h>
using namespace std;

const int N=15;

int n;
int p[N];
int group[N][N];
bool st[N];
int ans=N;

bool check(int g, int gc, int x){
    for(int i=0;i<gc;i++)
        if(__gcd(group[g][i], x) > 1)
            return false;
    return true;
}

void dfs(int sta, // 组合的方式, 从哪个数开始讨论, 当前数加入当前组, 不加人
        int g, // 当前最后一组
        int gc, // 当前最后一组的元素个数
        int cnt // 已经给多少个数分组
    ){
    if(g>=ans) return ;// 优化 
    if(cnt==n) ans=min(ans, g);

    bool flag=true;
    for(int i=sta;i<n;i++){
        if(st[i]) continue;

        if(check(g, gc, p[i])){
            st[i]=true;
            group[g][gc]=p[i];
            dfs(i+1, g, gc+1, cnt+1);
            st[i]=false;

            flag=false;
        }
    }

    if(flag) dfs(0, g+1, 0, cnt);// 没有数能加入当前组,新建组
}

void work(){
    cin>>n;

    for(int i=0;i<n;i++) cin>>p[i];

    dfs(0, 1, 0, 0);

    cout<<ans<<endl;
}

int main(){
    work();
    return 0;
}