11月16日星期天 9:00-12:00

S07L06 卒的遍历

描述

在一张n*m的棋盘上（如6行7列）的最左上角（1,1）的位置有一个卒。该卒只能向下或者向右走，且卒采取的策略是先向下，下边走到头就向右，请问从（1,1）点走到（n,m）点可以怎样走，输出这些走法。

输入描述

两个整数n，m代表棋盘大小（3=<n<=8,3<=m<=8）

输出描述

卒的行走路线

用例输入 1

3 3

用例输出 1

1:1,1->2,1->3,1->3,2->3,3
2:1,1->2,1->2,2->3,2->3,3
3:1,1->2,1->2,2->2,3->3,3
4:1,1->1,2->2,2->3,2->3,3
5:1,1->1,2->2,2->2,3->3,3
6:1,1->1,2->1,3->2,3->3,3

代码

#include<bits/stdc++.h>
using namespace std;
int num[10][10],n,m,num2[100][2],jishu;
int fx[2]={1,0};
int fy[2]={0,1};
void print(int k){
    jishu++;
    //1:1,1->2,1->3,1->3,2->3,3
    cout<<jishu<<":";
    for(int i=1;i<=k;i++){
        cout<<num2[i][0]<<","<<num2[i][1];
        if(i!=k){
            cout<<"->";
        }
    }cout<<endl;
}
void dfs(int x,int y,int k){
    //1.把走过的路存起来,到达终点就输出
    //2.因为要求所有路径,所以走过的路不标记,递归只会往右和往下,到达终点就会停止递归,并输出当前来的路径
    //3.等下一条路径的时候还会覆盖
    num2[k][0] = x;
    num2[k][1] = y;
    if(x==n&&y==m){
        print(k);
    }
    for(int i=0;i<2;i++){
        int xx = fx[i]+x;
        int yy = fy[i]+y;
      //不能出界
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
            dfs(xx,yy,k+1);
        }
    }
}

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

#include<bits/stdc++.h>
using namespace std;
int n,m,num2[100][2],jishu;
int fx[2]={1,0};
int fy[2]={0,1};
void print(int k){
    jishu++;
    //1:1,1->2,1->3,1->3,2->3,3
    cout<<jishu<<":";
    for(int i=1;i<=k;i++){
        cout<<num2[i][0]<<","<<num2[i][1];
        if(i!=k){
            cout<<"->";
        }
    }cout<<endl;
}
void dfs(int x,int y,int k){
    //1.把走过的路存起来,到达终点就输出
    //2.因为要求所有路径,所以走过的路不标记,递归只会往右和往下,到达终点就会停止递归,并输出当前来的路径
    //3.等下一条路径的时候还会覆盖
    for(int i=0;i<2;i++){
        int xx = fx[i]+x;
        int yy = fy[i]+y;
        //不能出界
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
            int kk = k+1;
            num2[kk][0] = xx;
            num2[kk][1] = yy;
            if(xx==n&&yy==m){
                print(kk);
            }else{
                dfs(xx,yy,kk);
            }
        }
    }
}

int main(){
    cin>>n>>m;
    num2[1][0]=1;
    num2[1][1]=1;
    dfs(1,1,1);
    return 0;
}

S07L07 【基础】迷宫的所有路径

描述

已知一N×N的迷宫，允许往上、下、左、右四个方向行走，且迷宫中没有任何障碍，所有的点都可以走。现请你按照右、下、左、上顺序进行搜索，找出从左上角到右下角的所有路径。

输入描述

输入一个整数N（N<=5）代表迷宫的大小。

输出描述

按右、下、左、上搜索顺序探索迷宫，输出从左上角1,1点走到右下角N,N点的所有可能的路径。

用例输入 1

3

用例输出 1

1:1,1->1,2->1,3->2,3->3,3
2:1,1->1,2->1,3->2,3->2,2->3,2->3,3
3:1,1->1,2->1,3->2,3->2,2->2,1->3,1->3,2->3,3
4:1,1->1,2->2,2->2,3->3,3
5:1,1->1,2->2,2->3,2->3,3
6:1,1->1,2->2,2->2,1->3,1->3,2->3,3
7:1,1->2,1->2,2->2,3->3,3
8:1,1->2,1->2,2->3,2->3,3
9:1,1->2,1->2,2->1,2->1,3->2,3->3,3
10:1,1->2,1->3,1->3,2->3,3
11:1,1->2,1->3,1->3,2->2,2->2,3->3,3
12:1,1->2,1->3,1->3,2->2,2->1,2->1,3->2,3->3,3

代码

#include<bits/stdc++.h>
using namespace std;
int n,num[10][10],num2[100][2],jishu;
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
void print(int k){
    jishu++;
    //1:1,1->2,1->3,1->3,2->3,3
    cout<<jishu<<":";
    for(int i=1;i<=k;i++){
        cout<<num2[i][0]<<","<<num2[i][1];
        if(i!=k){
            cout<<"->";
        }
    }cout<<endl;
}
void dfs(int x,int y,int k){
    for(int i=0;i<4;i++){
        int xx = fx[i]+x;
        int yy = fy[i]+y;
        //不能出界
        if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&num[xx][yy]==0){
            int kk = k+1;
            num2[kk][0] = xx;
            num2[kk][1] = yy;
            num[xx][yy]=1;
            if(xx==n&&yy==n){
                print(kk);
            }
            dfs(xx,yy,kk);
            num[xx][yy]=0;
        }
    }
}
int main(){
    cin>>n;
    num2[1][0]=1;
    num2[1][1]=1;
    num[1][1]=1;
    dfs(1,1,1);
    return 0;
}

S07L08【基础】全排列的结果

描述

从键盘读入一个整数n（n<=6），请输出1~n中所有整数的全排列，按照由小到大输出结果，每组的n个数之间用空格隔开。

全排列的含义：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

如当n=3时，全排列的结果为：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

输入描述

一个整数n（n >= 1 && n <= 6）

输出描述

1~n中所有数的全排列的结果，按照由小到大输出，每行n个数

用例输入 1

3

用例输出 1

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 n,num[10],num2[10],jishu;
void dfs(int k){
    if(k>n){
        for(int i=1;i<=n;i++)
        cout<<num[i]<<" ";
        cout<<endl;
    }
    //判断有没有被标记 没有标记放入数组 并且标记 回溯的时候再清0
    for(int i=1;i<=n;i++){
        if(num2[i]==0){
            num[k] = i;
            num2[i] = 1;
            dfs(k+1);
            num2[i] = 0;
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    return 0;
}

作业 S07Z02奶牛和草丛

描述

奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。

在牧场地图中，每个草丛要么是单个“#”，要么是有公共边的相邻多个“#”。给定牧场地图，计算有多少个草丛。

例如，考虑如下5行6列的牧场地图

.#…

…#…

…#…#

…##

…#

这个牧场有3个草丛：一个在第一行，一个在第二列横跨了二、三行，一个在第三行横跨了三、四、五行。

输入描述

第一行包含两个整数R和C，中间用单个空格隔开。

接下来R行，每行C个字符，描述牧场地图。字符只有“#”或“.”两种。(1 <= R, C <= 100 )

输出描述

输出一个整数，表示草丛数。

用例输入 1

5 6
.#....
..#...
..#..#
....##
.....#

用例输出 1

3

代码

#include<bits/stdc++.h>
using namespace std;
char num[110][110];
int n,m,jishu;
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
void dfs(int x,int y){
    //走过的点标记为.
    num[x][y]='.';
    for(int i=0;i<4;i++){
        int xx = x+fx[i];
        int yy = y+fy[i];
        //判断是否出界 是否走过
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&num[xx][yy]=='#'){
            dfs(xx,yy);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>num[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //遇到# 把他当做起点开始搜索,并且把走过的点变成.  这样搜索多少次代表有多少个草丛
            if(num[i][j]=='#'){
                dfs(i,j);
                jishu++;
            }
        }
    }
    cout<<jishu;
    return 0;
}