题意：有n个摊子，m个爆米花，想花费最少去的店铺买到所有的口味的爆米花，找到每一列都为‘o’的最少行数。

分析：用dfs寻找最少路径

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char x;int a[20][20];int n,m;
int vis[20]={0};int ans=500;
void dfs(int x,int y,int cnt){//超时 
    if(y>=m){
        ans=min(ans,cnt);
        return;
    }
    for(int i=1;i<=n;i++){
        if(a[i][y+1]==1){
            if(vis[i]==0){
                vis[i]=1;
                dfs(i,y+1,cnt+1);
                vis[i]=0;    
            }
            else{
                dfs(i,y+1,cnt);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>x;
            if(x=='o')a[i][j]=1;
            else a[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i][1]==1){
            vis[i]=1;
            dfs(i,1,1);
            vis[i]=0;
        }
    }
    cout<<ans<<endl; 
}然后超时咯

不能一个一个深搜 那就一行一行搜

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char xx;int a[20][20];int n,m;
int vis[20]={0};int ans=500;
void dfs(int x,int cnt){
    if(x>n){
        for(int i=1;i<=m;i++){
            if(vis[i]==0)return;
        }
        ans=min(ans,cnt);
        return; 
    }
    dfs(x+1,cnt);//不去
    for(int i=1;i<=m;i++){
        if(a[x][i]==1)vis[i]++;
    }
    dfs(x+1,cnt+1);//去 
    for(int i=1;i<=m;i++){
        if(a[x][i]==1)vis[i]--;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>xx;
            if(xx=='o')a[i][j]=1;
            else a[i][j]=0;
        }
    }
    dfs(1,0);
    cout<<ans<<endl; 
}