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

S07L09【提高】素数环

描述

从1~n（2<=n<=10）这n个数，摆成一个环，要求相邻的两个数的和是素数，按照由小到大请输出所有可能的摆放形式。

比如：n = 4，输出形式如下

1:1 2 3 4
2:1 4 3 2
3:2 1 4 3
4:2 3 4 1
5:3 2 1 4
6:3 4 1 2
7:4 1 2 3
8:4 3 2 1
total:8

比如：n = 6，输出形式如下

1:1 4 3 2 5 6
2:1 6 5 2 3 4
3:2 3 4 1 6 5
4:2 5 6 1 4 3
5:3 2 5 6 1 4
6:3 4 1 6 5 2
7:4 1 6 5 2 3
8:4 3 2 5 6 1
9:5 2 3 4 1 6
10:5 6 1 4 3 2
11:6 1 4 3 2 5
12:6 5 2 3 4 1
total:12

输入描述

一个整数n（2<=n<=10）

输出描述

前若干行，每行输出一个素数环的解，最后一行，输出解的总数

用例输入 1

用例输出 1

代码

#include<bits/stdc++.h>
using namespace std;
int n,num[10],num2[10],jishu;//num排列 num2 标记这个数是否放过
//判断素数
bool check(int n){
    if(n==1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
// k当前放到第几位数了 i就是每次放入数的值
void dfs(int k){
    // 第一个和最后一个数的和 没有判断是否为素数 该怎么办?
    // 当我们放完n位数的时候,判断数组的第一位和最后一位相加是否为素数 然后输出
    if(k>n&&check(num[n]+num[1])){
        //1:1 2 3 4
        jishu++;
        cout<<jishu<<":";
        for(int i=1;i<=n;i++){
            cout<<num[i]<<" ";
        }cout<<endl;
    }
    for(int i=1;i<=n;i++){
        // 每放入一个i 当放入第二个数的时候 和前面放入的数相加 判断是否为素数
        if(num2[i]==0&&(k==1||check(i+num[k-1]))){
            num[k] = i;
            num2[i]=1;
            dfs(k+1);//递归放入下一位数
            num2[i]=0;
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<"total:"<<jishu;
    return 0;
}

S07Z08【提高】迷宫的路径？

描述

Mitch老鼠在森林里游玩，不小心走进了一个迷宫里面，这个迷宫是一个n行m列的矩阵，迷宫中有些格子是可以走的，有些格子是不能走的，能走的格子用“o”（小写字母o）表示，不能走的格子用“#”表示。

Mitch选择走出迷宫的策略是：先向右，如果右边走不通则选择向下，如果下边走不通则选择向左，如果左边走不通则选择向上；如果四个方向都走不通，则后退选择其他能走的路径。

Mitch从类似下图所示的迷宫的左上角（1,1）点进入迷宫（请注意：入口1,1和出口的n,m点都不是#），请问Mitch有哪些方法可以走出迷宫，走到（n,m）点；请编程求出所有可能的路径，输出这些路径，如果不存在任何的路径可以走出迷宫，请输出“no”。

	1	2	3	4	5
1	o	o	o	o	o
2	o	#	#	#	#
3	o	o	o	o	o
4	#	o	o	#	o
5	o	o	o	o	#
6	o	#	o	o	o

输入描述

第一行包含两个整数n和m，中间用单个空格隔开，代表迷宫的行和列的数量。

接下来n行，每行m个字符，描述迷宫地图。字符只有“o”或“#”两种，“o”代表这个格子可以走，“#”代表这个格子不能走。(4 <= n,m <= 10 )

输出描述

请按照Mitch选择的走出迷宫的策略，输出所有可能的路径，输出形式请参考样例输出的形式。

用例输入 1

6 5
ooooo
o####
ooooo
#oo#o
oooo#
o#ooo

用例输出 1

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

代码

#include<bits/stdc++.h>
using namespace std;
char num[20][20];
int n,m,num2[400][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->4,3->5,3->5,4->6,4->6,5
    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<=m&&num[xx][yy]=='o'){
            int kk = k+1;
            num2[kk][0] = xx;
            num2[kk][1] = yy;
            num[xx][yy]='#';
            //走到终点打印 
            if(xx==n&&yy==m){
                print(kk);
            }
            dfs(xx,yy,kk);
            num[xx][yy]='o';
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		cin>>num[i][j];
		}
	} 
    num2[1][0]=1;//记录来的坐标 行坐标代表第几步 
    num2[1][1]=1;
    num[1][1]='#';//走过 标记为障碍物 
    dfs(1,1,1);
    //没有路径可走输出为no 
    if(jishu==0) cout<<"no";
    return 0;
}

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

S07L09【提高】素数环

描述

输入描述

用例输入 1

用例输出 1

代码

S07Z08【提高】迷宫的路径？

描述

输入描述

输出描述

用例输入 1

用例输出 1

代码

作业S07Z03