搜索与搜索剪枝

牛客网 2021秋季算法入门班第六章习题：搜索与搜索剪枝

1001 全排列

• DFS 回溯

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

bool is[10] = {0} ;
int path[10];

void dfs(int n){
    if(n == 8){
        for(int i = 0 ; i < 8 ; i ++){
            cout << path[i] << " " ;
        }
        cout << endl ;
    }
    
    for(int i = 1 ; i <= 8 ; i ++ ){
        if(!is[i]){
            path[n] = i ; 
            is[i] = true ;
            dfs(n + 1);
            is[i] = false ;
        }
    }
}

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

1002 走出迷宫

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

int main(){
    vector<vector<int>> direction = {{1,0},{-1,0},{0,1},{0,-1}} ;
    char ma[501][501] ;
    queue<pair<int , int>> que ;
    int visit[501][501] ;
    memset(visit, 0, sizeof(visit)); // init
    int n , m ;
    while(cin >> n >> m){
            for(int i = 0 ; i < n ; i ++){
                for(int j = 0 ; j < m ; j ++){
                    cin >> ma[i][j] ;
                    if(ma[i][j] == 'S'){
                        que.push({i , j});
                        visit[i][j] = 1 ;
                    }
                }
            }
        while(!que.empty()){
            auto preque = que.front();
            que.pop();
            int x = preque.first , y = preque.second ;
            for(int i = 0 ; i < 4 ; i ++){
                int prex = direction[i][0] + x , prey = direction[i][1] + y ;
                if(prex >= 0 && prex < n && prey >= 0 && prey < m && ma[prex][prey] == '.' && visit[prex][prey] == 0){
                    que.push({prex , prey});
                    visit[prex][prey] = 1 ;
                }
                if(ma[prex][prey] == 'E'){
                    cout << "Yes" << endl;
                }
            }
        }

        cout << "No" << endl;
    }
    return 0 ;
}

由于有多组输入，所以用 while 输入，不然会在第一组数据回城。

• 过了 75% 用例

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

int main(){
    vector<vector<int>> direction = {{1,0},{-1,0},{0,1},{0,-1}} ;
    char ma[501][501] ;
    queue<pair<int , int>> que ;
    int visit[501][501] ;
    memset(visit, 0, sizeof(visit)); // init
    int n , m ;
    while(cin >> n >> m){
        int flag = 0 ;
            for(int i = 0 ; i < n ; i ++){
                for(int j = 0 ; j < m ; j ++){
                    cin >> ma[i][j] ;
                    if(ma[i][j] == 'S'){
                        que.push({i , j});
                        visit[i][j] = 1 ;
                    }
                }
            }
        while(!que.empty()){
            auto preque = que.front();
            que.pop();
            int x = preque.first , y = preque.second ;
            for(int i = 0 ; i < 4 ; i ++){
                int prex = direction[i][0] + x , prey = direction[i][1] + y ;
                if(prex >= 0 && prex < n && prey >= 0 && prey < m && ma[prex][prey] == '.' && visit[prex][prey] == 0){
                    que.push({prex , prey});
                    visit[prex][prey] = 1 ;
                }
                if(ma[prex][prey] == 'E'){
                    flag = 1 ;
                }
                if(flag == 1) break ;
            }
        }
        if(flag == 1) cout << "Yes" << endl ;
        else cout << "No" << endl;
    }
    return 0 ;
}

• AC

#include <bits/stdc++.h>
using namespace std;
char mp[501][501];
int _next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int visit[501][501];
void init(){
    memset(visit,0,sizeof(visit));
}
 
int main(){
    int n,m;
    while(cin>>n>>m){
        int bx,by;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>mp[i][j];
                if(mp[i][j]=='S'){
                    bx=i;
                    by=j;
                }
            }
        }
        //cout<<bx<<" "<<by<<endl;
        init();
        queue<pair<int,int>>q;
        q.push(make_pair(bx,by));
        visit[bx][by]=1;
        int flag=0;
        while(!q.empty()){
            pair<int,int>x=q.front();
             
            q.pop();
            for(int i=0;i<4;i++){
                int c=x.first+_next[i][0];
                int d=x.second+_next[i][1];
                if(c<n&&d<m&&c>=0&&d>=0&&mp[c][d]=='.'&&!visit[c][d]){
                    q.push(make_pair(c,d));
                    visit[c][d]=1;
                }
                if(c<n&&d<m&&c>=0&&d>=0&&mp[c][d]=='E'){
                    flag=1;
                    break;
                }
            }  
            if(flag==1){
                break;
            }      
        }
        if(flag==1){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
     
    return 0;
}