试题 E: 迷宫

来源：2019 第十届蓝桥杯C/C++ 省赛B组
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D < L < U < R
（请各位自行创建maze.txt并使用文件读写）
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
输入描述：

无

输出描述：

本题的结果为一个字符串，包含四种字母 D、U、L、R

示例 1：
输入：

无

输出：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
(maze.txt的答案)

扫雷游戏

来源：牛客网
扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。
现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。
注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

输入描述：

输入文件第一行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。
接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格，字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。

输出描述：

输出文件包含n行，每行m个字符，描述整个雷区。用’*’表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。

示例 1：
输入：

3 3
*??
???
?*?

输出：

*10
221
1*1

示例 2：
输入：

2 3
?*?
*??

输出：

2*1
*21

乒乓球

来源：牛客网
国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。
华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。
比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：
WWWWWWWWWWWWWWWWWWWWWWLW
在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。
你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果

输入描述：

每次输入包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。

输出描述：

输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。
第一部分是11分制下的结果；
第二部分是21分制下的结果，两部分之间由一个空行分隔。

示例 1：
输入：

WWWWWWWWWWWWWWWWWWWW
WWLWE

输出：

11:0
11:0
1:1

21:0
2:1

第 k 个缺失的正整数

来源：力扣
给你一个严格升序排列的正整数数组 arr 和一个整数 k
请你找到这个数组里第 k 个缺失的正整数
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]

输入描述：

第一行输入两个整数为k,n
第二行输入n个整数为严格升序排列的正整数数组arr

输出描述：

输出一个数字代表第k个缺失的正整数

示例 1：
输入：

5 5
2 3 4 7 11

输出：

9

示例 1：
输入：

2 4
1 2 3 4

输出：

6

食物链

来源：牛客网
如图所示为某生态系统的食物网示意图，据图回答第1小题
现在给你n个物种和m条能量流动关系，求其中的食物链条数。
物种的名称为从1到n编号
M条能量流动关系形如
a1 b1
a2 b2
a3 b3
......
am-1 bm-1
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链
输入描述：

第一行两个整数n和m,接下来m行每行两个整数ai，bi描述m条能量流动关系。（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）
1 ≤ N ≤ 100000，0 ≤ m ≤ 200000
题目保证答案不会爆 int

输出描述：

一个整数即食物网中的食物链条数

示例 1：
输入：

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

输出：

9

最长上升子序列

来源：力扣
给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入描述：

第一行输入一个整数n
第二行输入n个整数为无序的整数数组

输出描述：

输出一个整数，代表最长上升子序列的长度

示例 1：
输入：

8
10 9 2 5 3 7 101 18

输出：

4

排列数

来源：蓝桥练习系统
0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
0 < n <= 10!
求0~9十个数的全排列中按字典序的第n个（第1个为0123456789）

输入描述：

一行，包含一个整数n

输出描述：

一行，包含一组10个数字的全排列

示例 1：
输入：

1

输出：

0123456789