第三章 搜索与图论

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

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

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

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

数据范围

输入样例：

输出样例：
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。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8