2022.09全国青少年软件编程（C语言）等级考试试卷（五级）

2022年九月C语言五级试题 一、城堡问题 1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # # | | | | # # ############################# (图 1) # = Wall | = No wall - = No wall 图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m×n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。 时间限制：1000 内存限制：65536 输入 程序从标准输入设备读入数据。第1、2行每行1个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。 输出 输出2行，每行一个数，表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。 样例输入 4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 样例输出 5 9 二、斗地主大师     斗地主大师今天有P个欢乐豆，他夜观天象，算出了一个幸运数字Q，如果他能有恰好Q个欢乐豆，就可以轻松完成程设大作业了。 斗地主大师显然是斗地主大师，可以在斗地主的时候轻松操控游戏的输赢。 1.他可以轻松赢一把，让自己的欢乐豆变成原来的Y倍 2.他也可以故意输一把，损失X个欢乐豆(注意欢乐豆显然不能变成负数，所以如果手里没有X个豆就不能用这个能力) 而斗地主大师还有一种怪癖，扑克除去大小王只有52张，所以他一天之内最多只会打52把斗地主。 斗地主大师希望你能告诉他，为了把P个欢乐豆变成Q个，他至少要打多少把斗地主？ 时间限制：1000 内存限制：65536 输入 第一行4个正整数 P,Q,X,Y 0< P,X,Q <= 2^31, 1< Y <= 225 输出 输出一个数表示斗地主大师至少要用多少次能力 如果打了52次斗地主也不能把P个欢乐豆变成Q个，请输出一行 "Failed" 样例输入 输入样例1： 2 2333 666 8 输入样例2： 1264574 285855522 26746122 3 样例输出 输出样例1： Failed 输出样例2： 33 提示 可以考虑深搜 要用long long 三、玩具摆放 在一个4*4的方框内摆放了若干个相同的玩具。 某人想通过移动玩具，将这些玩具重新摆放成为他心中理想的状态。要求每次移动时，只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框，并且移动的目标位置不能已经放置有玩具。   请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。 时间限制：10000 内存限制：524288 输入 前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。 输出 一个整数，所需要的最少移动次数。保证初始状态可以达到目标状态。 样例输入 1111 0000 1110 0010 1010 0101 1010 0101 样例输出 4 提示 可以考虑将玩具局面表示为一个16 bit的整数，设置一个标志数组用来判重，用这个整数做下标找其对应标志位 四、哥斯拉大战金刚 众所周知，哥斯拉和金刚是时代仇敌，大战一触即发。金刚为了打败哥斯拉，要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图，S表示金刚目前的位置，T表示地心空洞的入口，X表示障碍物，.表示平地。在前往地心空洞之前，金刚必须先获得一系列打开地心空洞的钥匙（在地图上通过数字1,2,…,k表示），并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙，金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外，同一种类的钥匙可能有多把，金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格，值得注意的是，哥斯拉为了阻挠金刚的计划，还在地图上设置了q个陷阱（在网格图中用G表示），金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱（这之后该陷阱即可被视为平地）。为了更好的掌握全局，请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。 时间限制：6000 内存限制：262144 输入 第一行输入两个整数n,m，表示网格图的大小。 接下来n行，每行输入m个字符，表示地图 1 ≤ n,m ≤ 100 1 ≤ k ≤ 9 1 ≤ q ≤ 7 输出 输出一行包含一个整数，表示金刚到达地心空洞入口所需要花费的最少步数。 样例输入 5 5 XX13X X.GXX S...T XXGXX ....2 样例输出 24 学科网（北京）股份有限公司 $$