第三章搜索与图论

2021-04-10 本文已影响0人 burningrain

AcWing 842. 排列数字
给定一个整数 $n$ ，将数字 $1到n$ 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 $n$ 。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
$1≤n≤7$
输入样例：
$3$
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
代码：

#include<bits/stdc++.h>
using namespace std;
int vis[10];
int n;
int path[10];
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<path[i]<<" ";
        }cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
          if(!vis[i]){
              path[u]=i;
              vis[i]=1;
              dfs(u+1);
              path[u]=0;
              vis[i]=0;
          }
    }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10];
void dfs(int low,int hight){
    if(low==hight){
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }cout<<endl;
    }
    int x=0;
    for(int i=low;i<=hight;i++){
        x=a[low];
        a[low]=a[i];
        a[i]=x;
        dfs(low+1,hight);   
        x=a[low];
        a[low]=a[i];
        a[i]=x;
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){a[i]=i;}
    dfs(1,n);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){a[i]=i;}
    do{
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }cout<<endl;
    }while(next_permutation(a+1,a+1+n));
    return 0;
}

843. n-皇后问题

#include<bits/stdc++.h>
using namespace std;
int n;
int col[100],gd[200],ugd[200];
char g[100][100];
void dfs(int x){
    if(x==n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<g[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
        return;
    }
    for(int y=0;y<n;y++){
        if(!col[y]&&!gd[x+y]&&!ugd[y-x+n]){
            col[y]=gd[x+y]=ugd[y-x+n]=1;
            g[x][y]='Q';
            dfs(x+1);
            col[y]=gd[x+y]=ugd[y-x+n]=0;
            g[x][y]='.';
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

AcWing 844. 走迷宫
给定一个 $n*m$ 的二维整数数组，用来表示一个迷宫，数组中只包含 $0$ 或 $1$ ，其中 $0$ 表示可以走的路， $1$ 表示不可通过的墙壁。