专栏首页Tanger的思源地ACM之7-25日作业题解

ACM之7-25日作业题解

1.A:六皇后

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出,解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。

1.A:六皇后

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i个数字表示在第i行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出,解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。

输入

一行一个正整数 n,6≤n≤13,表示棋盘是 nxn大小的

输出

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

样例输入

6

样例输出

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

参考程序(自己打的)

#include<iostream>
using namespace std;
int count = 0;
int chess[6][6]={0};
int notDanger(int row,int col ){
    int i,k;
    for(i=0;i<6;i++){
        if(chess[i][col]==1)
        return 0;
    }
    for(i=row,k=col;i>=0&&k>=0;i--,k--)
    if(chess[i][k]==1)
    return 0;
    
    for(i=row,k=col;i>=0&&k<6;i--,k++)
    if(chess[i][k]==1)
    return 0;
    
    return 1;
}

void Print(){
    int i,j;
    for(i=0;i<6;i++){
        for(j=0;j<6;j++){
            if(chess[i][j]==1)
            cout<<j+1<<" ";
        }
    }
    cout<<endl;
}
void EightQueen( int row ){
    int col;
    if( row>5 )                       {
        Print();                      
        count++;
        return ;}

题解:写得十分长,但是该有的东西还是有的,比如判断的函数,还有输出以及循环的函数,这里没用到搜索,只是枚举,详细请见ACM之“八皇后”

2.B:东南西北

题目描述

给出起点和终点的坐标及接下来T个时刻的风向(东南西北),每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少步数。

如果无法偏移至终点,输出“-1”。

输入

第一行两个正整数x1,y1,表示小明所在位置。

第二行两个正整数x2,y2,表示小明想去的位置。

第三行一个整数T,表示T个时刻。1<=T<=50

第四至第N+3行,每行一个字符,表示风向,即东南西北的英文单词的首字母

输出

最少走多少步。

样例输入

1 1
2 2
5
E
N
W
W
N

样例输出

2

参考程序

#include <iostream>
using namespace std;
int x,y,x1,y1,n,s=0;
char a;
int l=0;
int main()
{
    cin>>x>>y>>x1>>y1;
    cin>>n;
    if(x==x1&&y==y1){cout<<'0';return 0;}
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(x1-x>0&&a=='E')x++,s++;
        else if(x1-x<0&&a=='W')x--,s++;
        if(y1-y>0&&a=='N')y++,s++;
        else if(y1-y<0&&a=='S')y--,s++;
    }
    if(x==x1&&y==y1)cout<<s;
    else cout<<"-1";
    return 0;
}

题解

只要边输入边看这个方向是不是朝着终点。如果是,就动。否则就不动。

3.C:跳马

题目描述

中国象棋半张棋盘如图 11 所示。马自左下角 (0,0)(0,0) 向右上角 (m,n)(m,n) 跳。规定只能往右跳,不准往左跳。比如图 11 中所示为一种跳行路线,并将路径总数打印出来。

输入

只有一行:两个数 n,m。0<=n,m≤18

输出

输出一个数:马从左下角到右上角的总方案数 total。

样例输入

4 8

样例输出

37

参考程序

#include <stdio.h>
#include <queue>
using namespace std;
int dx[4]= {1, 2, 1, 2};
int dy[4]= {2, 1, -2, -1};//四种走法
int ways=0;//记录路线条数

struct NODE {
    int x, y;
};//记录路线上的点的坐标

bool Valid (NODE h, int m, int n) {
    if ((h.x<=m)&&(h.y>=1)&&(h.y)<=n)
        return 1;
    else
        return 0;
}//判断下的这步棋是否符合规则

bool bfs (NODE s, int m, int n) {
    queue<NODE>q;//建立路线队列
    NODE now, next;//用于记录当前棋和进入下一步的棋
    q.push(s);//起点入列
    while (!q.empty()) {
        now = q.front();
        q.pop();//取出当前棋子并出列
        if ((now.x==m)&&(now.y==n)) {
            ways++;
            continue;
        }//判断是否走到终点
        for ( int i=0; i<4; i++) {
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];//走出四种走法
            if (Valid(next,m, n))
                q.push(next);//如果有效则入列
        }
    }
}

int main() {
    int m, n;
    scanf ("%d %d", &m, &n);
    NODE s;
    s= {1,1};//起点
    bfs (s, n, m);//开始搜索
    printf ("%d\n", ways);
    return 0;
}

题解:

搜索中的经典问题,跟help庞学姐类似

4.D:奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼(1≤i≤N)上有一个数字K(0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3, 3 ,1 ,2 ,5代表了Ki (K 1 =3,K 2 =3,…),从11楼开始。在1楼,按“上”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮呢?

输入

共二行。

第一行,为3个用空格隔开的正整数, 表示N,A,B

第二行,为N个用空格隔开的非负整数, 表示K_i

输出

一行,即最少按键次数,若无法到达,则输出−1。

样例输入

5 1 5
3 3 1 2 5

样例输出

3

参考程序

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    queue<int> q;  //BFS 实现用队列
    vector<int> v; //保存每层按钮上的数值
    vector<int> f; //到达每层最少的按键次数
    vector<bool> flag;//标记值,表示每层是否被访问过,true代表访问过
    int n;
    int start, end;//开始层和结束层
    int tmp;
    cin >> n >> start >> end;
    v.push_back(0);//方便起见,下标从1开始
    f.push_back(0);
    flag.push_back(false);
    for (int  i = 1; i <= n; i++)
    {
        cin >> tmp;
        v.push_back(tmp);
        if(i == start)
            f.push_back(0);//初始化,start层开始为按0次,其余层为-1次
        else
            f.push_back(-1);
        flag.push_back(false);
    }
    q.push(start);

    while (!q.empty()&& !flag.at(q.front()))//队列不为空,切第q.front()层没有被访问过
    {
        flag.at(q.front()) = true;
        int next = q.front() + v.at(q.front());
        if (next <= n) //上楼
        {
            q.push(next);
            f.at(next) = f.at(q.front()) + 1;//记下到达每层最少的按键次数
            if (next == end) //找到end层,退出while循环
            {
                break;
            }
        }
        next = q.front() - v.at(q.front());
        if (next >= 1)//下楼
        {
            q.push(next);
            f.at(next) = f.at(q.front()) + 1;
            if (next == end)//找到end层,退出while循环
            {
                break;
            }
        }
        q.pop();
    }
    cout << f.at(end) << endl;

    return 0;
}

题解

动态分配内存,采用STL的vector容器来解答,也可以简单的用数组来实现

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ACM之7-23日作业题解

    给你一个数组a,注意下标从0开始 如果数组中的每个奇数下标为奇数且数组中的每个偶数的下标为偶数则叫好数组否则就是不好数组 比如...

    Tanger
  • ACM之7-22日作业题解

    一天,天上掉下来了一个可爱的小妹妹,小妹妹天天缠着你给她讲故事。并且让你在N天内给她讲K(K ≤ N)个不同小故事。你把你知道的所有K个故事从1到K进行编...

    Tanger
  • ACM之7.21日作业题解

    题解:这里的A是用来存放各位数的一个数组因为最多只有10个不同的数字所以A[10]恰好 够用,result[300]是用来打标记的,用过的数组就改false为t...

    Tanger
  • ACM之7-25日中期比赛

    给你一个由n个整数组成的数组a。 在一次移动中,您可以选择两个下标 1≤i,j≤n,i≠j并且设置ai:=aj。您可以执行这样的移动任意次数(可能是零次)。您可...

    Tanger
  • 浙江理工大学 我的编程之路 零基础学C/C++ 200题 标程/题解

    标程/题解GitHub:https://github.com/ZSTUCA-TEAM/zstuACM/tree/main/200

    用户7886150
  • 最全2019 AI/计算机/机器人顶会时间表来了,共收录36场会议,投稿冲鸭!

    下面,是量子位给大家整理的2019 AI顶会时间表,包含会议举办的时间、地点、投稿截止日期、官方网址/社交媒体地址,还有H5指数(谷歌学术的期刊会议评判标准,即...

    量子位
  • 2021年7月国产数据库排行榜:openGauss成绩依旧亮眼,Kingbase向Top 10发起冲刺

    7月份的国产数据库流行度排行榜已经揭晓。本期榜单展示的136个数据库中,近三分之二实现了评分增长。笔者认为这与6月份中国信通院发布第十二批大数据产品能力评测结果...

    数据和云
  • 【学术盛宴 】多媒体顶级会议ACM Multimedia 2017 China Pre-conference论文宣讲研讨会

    【导读】第25届ACM国际多媒体会议(ACM International Conference on Multimedia, 简称ACMMM)于2017年10月...

    WZEARW
  • 【推荐系统教程】当机器学习遇到推荐系统,悉尼科技大学Liang Hu博士最新分享

    【导读】第32届AAAI大会-AAAI 2018将于2月2号-7号在美国新奥尔良召开,悉尼科技大学Liang Hu博士即将在大会作报告“When Advance...

    WZEARW
  • 是男人就过8题!楼教主出题,请接招

    用户1737318
  • 周末荐

    腾讯技术工程官方号
  • 第一个世界量子日,量子计算大牛Scott Aaronson获颁ACM计算奖

    刚刚,理论计算机科学家、UT Austin 教授、量子计算先驱 Scott Aaronson 因其「对量子计算的开创性贡献」被授予 2020 年度 ACM 计算...

    机器之心
  • 【专知荟萃07】自动文摘AS知识资料全集(入门/进阶/代码/数据/专家等)(附pdf下载)

    【导读】主题荟萃知识是专知的核心功能之一,为用户提供AI领域系统性的知识学习服务。主题荟萃为用户提供全网关于该主题的精华(Awesome)知识资料收录整理,使得...

    WZEARW
  • AI 人才遭疯抢,Google 为 22 岁印度毕业生开出 1000w+ 年薪

    他就是仅有 22 岁的 Aditya Paliwal。2013 年到 2018 年,Aditya Paliwal 参加了为期五年的计算机综合 M.Tech 双学...

    IT派
  • 2018图灵奖重磅公布!体系结构宗师John Hennessy和David Patterson获奖!会师谷歌

    John Hennessy(左)和David Patterson 拿着他们合著的《计算机体系架构:量化研究方法》,照片的拍摄时间大约是1991年。来源:ACM ...

    新智元
  • 北大主场夺金ACM-ICPC全球总决赛,总教练罗国杰分享背后“秘笈”

    昨天(4月19日)下午,第42届ACM-ICPC国际大学生程序设计竞赛全球总决赛,在北京大学邱德拔体育馆举行,这也是2005年上海、2010年哈尔滨之后,中国第...

    量子位
  • 2018年机器学习和数据科学重要会议概览

    来源:KDnuggets 编译:Bing 一月 美洲 BAFI 2018:金融和工业商业分析第三次会议(3rd Conf. on Business Analyt...

    企鹅号小编
  • 悬赏题No.1 - 扑克牌

    ACM算法日常推出悬赏题啦,悬赏题一般是平时日常听闻的题目,题意简单,结构稍微复杂,并且不知道算法的结果,需要解题者在理解题意的情况下给出合理的解决方案和结果...

    ACM算法日常
  • 重磅 | 万维网之父 Tim Berners-Lee 荣获2016年度图灵奖

    用户1737318

扫码关注云+社区

领取腾讯云代金券