3.8深度优先搜索dfs

P1706 全排列问题

【题目描述】
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，
要求所产生的任一数字序列中不允许出现重复的数字。

【输入格式】
一个整数 n。

【输出格式】
由 1～n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个场宽。

输入样例: 3
输出样例:

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

说明/提示：1≤n≤9。

【参考题解】

#include
using namespace std;
int n, a[10],vis[10];
void print(){
    for(int i=1; i<=n; i++){
        printf("%5d",a[i]);//cout<n){// Why not? m>=n, Because: true == (a[m]==0);
        print(); return ;//返回上一级，可以节省少许时间
    }
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            a[m] = i;  vis[i] = 1;
            dfs(m+1);    // 继续安置第 m+1 列的元素
            vis[i] = 0;  //回溯，当前元素取消使用标记
        }
    }
}
int main(){
    scanf("%d", &n);
    dfs(1);
    return 0;
}

P1157 组合的输出

【题目描述】
排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r≤n)，
我们可以简单地将 n 个元素理解为自然数 1,2,…,n，从中任取 r 个数。
现要求你输出所有组合。

【输入格式】
一行两个自然数 n,r (1

【输出格式】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，
每个元素占三个字符的位置，所有的组合也按字典顺序。

输入样例: 5 3
输出样例:

  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

【参考题解】

#include
#include
using namespace std;
const int N=21;
int n, r, a[N], vis[N];
void dfs(int m){
    if(m>r){
        for(int i=1; i<=r; i++){
            cout<a[m-1]){
            a[m] = i; vis[i] = 1;
            dfs(m+1);
            vis[i] = 0; //回溯
        }
    }
    return;
}

int main(){
    cin>>n>>r;
    dfs(1);
    return 0;
}

P1605 迷宫

【题目描述】
给定一个 N*M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

【输入格式】
第一行N、M和T，N为行，M为列，T为障碍总数。
第二行起点坐标 SX,SY，终点坐标 FX,FY。接下来 T 行，每行为障碍点的坐标。

【输出格式】
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

输入样例:

2 2 1
1 1 2 2
1 2

输出样例: 1
说明/提示: 1≤N,M≤5

【参考题解】

#include
using namespace std;
const int N=10;
int a[N][N],vis[N][N];
int n, m, t, x1, x2, y1, y2, ans=0;

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

void dfs(int x, int y){
    if(x<1 || y<1 || x>n || y>m ||a[x][y]==1) return;
    if(x==x2 && y==y2){
        ans++; return;
    }
    a[x][y]=1;//一个点只能走一次
    for(int i=0; i<4; i++){
       dfs(x+dx[i], y+dy[i]);
    }
    a[x][y]=0;
}

int main(){
    cin>>n>>m>>t;
    cin>>x1>>y1>>x2>>y2;
    for(int i=1; i<=t; i++) {
        int x,y; cin>>x>>y;
        a[x][y]=1;
    }
    dfs(x1,y1);
    cout<

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

#include
using namespace std;

const int N=55;
int h,w,ans=0;
char a[N][N];
int dis[][2]={{-1, 0},{ 0,-1},{ 1, 0},{ 0, 1}};

void print(){
    for(int i=0; i=0 && x=0 && y

1 1 1
2 3

1 1 3
8 8

#include
#include
using namespace std;
const int N=30;
int vis[N][N];
int dis[][2]={
{-2, -1},{-1,-2},{ 1,-2},{ 2,-1},
{ 2,  1},{ 1, 2},{-1, 2},{-2, 1}};

bool in(int x,int y){
    if(x>=1 && x<=8 && y>=1 && y<=8) return 1;
    return 0;
}

void print(){
    for(int i=1; i<=8; i++){
        for(int j=1; j<=8; j++){
            printf("%d", vis[i][j]);
        }printf("\n");
    }printf("\n");
}

void dfs(int x, int y, int step){
    vis[x][y]=step+1;
//    print(); //输出调试
    if(step<=0) return; // 0步特殊处理
    for(int i=0; i<8; i++){
        int tx=x+dis[i][0];
        int ty=y+dis[i][1];// 如果当前步数过小，就被更新
        if(in(tx,ty) && step>0 && vis[tx][ty]>x>>y>>c>>a>>b;

    dfs(x,y,c);
    if(vis[a][b]) cout<<"yes";
    else cout<<"no";
    return 0;
}