算法 搜索DFSBFS
[TOC]
二分
leetcode 392. 判断子序列
问题描述
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
示例 1:
s = "abc"
, t = "ahbgdc"
返回 true
.
示例 2:
s = "axc"
, t = "ahbgdc"
返回 false
.
思路二分法
- 用哈希集合hase_set记录下t中每个字符出现过的位置,即最多有26个key
- 对s中每个字母进行匹配,s[i]一定出现在s[i-1]之后,所以匹配s[i]的时候,应该找hash_set[s[i]]中大于s[i-1]的索引的索引值
- 我们用匹配左边界的二分法(即匹配第一个大于等于目标值的数),找当前字母索引列表中第一个大于上一个字母索引的值
- 如果某个匹配到的边界值等于当前字幕索引列表的长度,则表明无法匹配当前字母,返回False
- 全部成功匹配返回True
1 | boolean isSubsequence(String s, String t) { |
BFS
BFS模板
1 | void BFS(){ |
填涂颜色
题目描述
由数字00组成的方阵中,有一任意形状闭合圈,闭合圈由数字11构成,围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如:6 \times 66×6的方阵(n=6n=6),涂色前和涂色后的方阵如下:
1 | 输入: |
1 | import java.util.LinkedList; |
马的遍历
题目描述
有一个n*m的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式
一行四个数据,棋盘的大小和马的坐标
输出格式
一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)
输入
1 | 3 3 1 1 |
输出
1 | 0 3 2 |
1 | package luogu; |
奇怪的电梯
题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼 (1≤i≤N) 上有一个数字Ki (0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3, 3 ,1 ,2 ,53,3,1,2,5代表了Ki(K1=3,K2=3,…)Ki(K1=3,K2=3,…),从11楼开始。在11楼,按“上”可以到44楼,按“下”是不起作用的,因为没有-2−2楼。那么,从AA楼到BB楼至少要按几次按钮呢?
输入格式
共二行。
第一行为3个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N)。
第二行为N个用空格隔开的非负整数,表示Ki。
输出格式
一行,即最少按键次数,若无法到达,则输出−1。
输入
1 | 5 1 5 |
输出
1 | 3 |
1 | package luogu; |
01迷宫
题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上,那么你可以移动到相邻4格中的某一格1上,同样若你位于一格1上,那么你可以移动到相邻4格中的某一格0上。
你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。
输入格式
第1行为两个正整数n,m。
下面n行,每行n个字符,字符只可能是0或者1,字符之间没有空格。
接下来m行,每行22个用空格分隔的正整数i,j,对应了迷宫中第i行第j列的一个格子,询问从这一格开始能移动到多少格。
输出格式
m行,对于每个询问输出相应答案。
输入输出样例
输入 #1
1 | 2 2 |
输出 #1
1 | 4 |
说明/提示
所有格子互相可达。
对于20%20%的数据,n≤10n≤10;
对于40%40%的数据,n≤50n≤50;
对于50%50%的数据,m≤5m≤5;
对于60%60%的数据,n≤100,m≤100n≤100,m≤100;
对于100%100%的数据,n≤1000,m≤100000n≤1000,m≤100000。
1 | package luogu; |
蓝桥杯迷宫
要求按字典序 打印轨迹
运行结果
1 | public class Main { |
字串变换
题目描述
已知有两个字串A,BA,B及一组字串变换的规则(至多6个规则):
A1 ->B1
A2 -> B2
规则的含义为:在 AA中的子串 A1 可以变换为B_1B1,A_2A2 可以变换为 B2 …。
例如:A=abcd
,B=xyz
,
变换规则为:
abc
→xu
,ud
→y
,y
→yz
则此时,AA可以经过一系列的变换变为BB,其变换的过程为:
abcd
→xud
→xy
→xyz
。
共进行了33次变换,使得AA变换为BB。
输入格式
输入格式如下:
AA BB
A1 B1
A2 B2 |-> 变换规则
… … /
所有字符串长度的上限为2020。
输出格式
输出至屏幕。格式如下:
若在1010步(包含1010步)以内能将AA变换为BB,则输出最少的变换步数;否则输出”NO ANSWER!”
输入
1 | abcd xyz |
输出
1 | 3 |
1 |
|
机器人搬重物
题目描述
机器人移动学会(RMI
)现在正尝试用机器人搬运物品。机器人的形状是一个直径1.61.6米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个 N \times MN×M 的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动11步(Creep
);向前移动2步(Walk
);向前移动33 步(Run
);向左转(Left
);向右转(Right
)。每个指令所需要的时间为11 秒。请你计算一下机器人完成任务所需的最少时间。
输入格式
第一行为两个正整数N,M(N,M \le 50)N,M(N,M≤50),下面NN行是储藏室的构造,00表示无障碍,11表示有障碍,数字之间用一个空格隔开。接着一行有44个整数和11个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东EE,南SS,西WW,北NN),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式
一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出-1−1。
输入
1 | 9 10 |
输出
1 | 12 |
这道题,毫无疑问,就是广搜。但是它要注意的细节非常多。所以这道题对逻辑和代码能力的的考察很高
首先,这道题需要注意,障碍物是在格子上,而机器人是在格点上走。某人就是我自信地写完了代码后发现题读错了。关键最讨厌的是样例居然能过……
那么这道题经过信息整理可以发现,我们需要两个数组:一个存方格上障碍物的位置(sd[i][j]数组表示),一个存机器人可以走的格点的位置(a[i][j])数组表示,则根据样例我们可以整理成这张图: 其中黑色为数组sd[i][j]的下标,绿色为a[i][j]的下标。根据题目可以发现,机器人本身也有宽度,所以边界和障碍物的四周,不能走,那么机器人可以到达的地方就是图中蓝色框内的绿色格点。所以边界条件判断时,n和m各要减1。
然后我们还需要注意的地方是题中害人不浅的方向处理。于是为了方便存储,我给每个方向都编了一个号:↑为1,↓为2,←为3,→为4。然后转向的时候就更加麻烦了。于是我为了好判断情况,emm……用了好几个数组
1 | int fx[5]={0,-1,1,0,0};//fx[i]表方向i(编号)的x的进退情况 |
其中ft数组和abc数组比较难理解
先讲abc数组 如图,不难看出当对于不同的i,也就是顺时针转动i次时,对应的最小旋转次数就是abc[i]
而ft数组也比较好理解 abc图中蓝圈内四个方向各有一个黑色数字代表方向编号,那么我们顺时针遍历一下就是1 4 2 3.
我么还要注意的地方是起点和终点可能重合,需要特判;起点可能就有障碍物,也要特判。
最后要注意的是,对于每一步,你走一个格点,两个格点或三个格点所耗时间都是1,不要搞乱;而每转90°,就要耗一定时间,所以千万要小心。
于是,开始写BFS
用队列存储每一个格点的信息,然后起点入队,每次从队首取出一个元素,根据这个元素旋转,直行,得到一个新的坐标,然后判断由这种方式到达的这个点是否是耗时最短的一种方式(类似于Dijkstra中的dis数组),此处用f[i][j]数组表示,然后队列为空后,输出f[终点的x][终点的y]
即可。
丧心病狂的代码如下
1 |
|
CoVH之再破难关/黑白棋
Problem
OIBH组织派出的黄金十二人+青铜五小强还没有到, 他们只能指望原先的机关能够阻拦住柯南的脚步.
柯南打开大门之后发现里面还有一个门, 门上还有一个神奇的锁(-,-)
这是一个4*4的锁, 上面有8个凸起的格子和8个被按下的格子
当且仅当两个格子有公共边时, 则称这两个格子是相邻的。
每次操作只能够交换相邻的两个格子
柯南看到了初始锁的状态 和目标锁的状态
同样组织只允许他用最少步数打开锁
输入格式
第1到4行每行四个数字(1或者0),描述了初始锁状态
接着是一个空行
第6到9行每行四个数字,描述了最终锁状态
输出格式
输出文件只有一行,是一个整数n,表示最少的操作次数。
1 | Input |
1 | /*还有一种是bfs+map判重+状态压缩 |
油田问题(java)
问题描述
GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。
Input
输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是’* ’,代表没有油,要么是’@’,表示有油。
Output
对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。
Sample Input
1 | 1 1 |
Sample Output
0
1
2
2
1 | import java.util.*; |
Whack-A-Mole
Problem
This time we’ll play a variation of Whack-A-Mole! We’ll play this game on a board with 16
holes, from which individual moles pop-up. Using a mallet you can then “whack a mole”
and make it go hide underground. As you might know, however, whacking a mole will
often have the effect of making other moles rise and come out from the ground. In this
version of the game, every time you hit a mole with the mallet you’ll cause the immediate
four adjacent holes to change: any moles currently there will hide, while new moles popup from previously empty holes.
Imagine, for example, that you find yourself in the following game configuration, and you
prepare yourself to hit the mole at position 10 with the mallet.
You will cause the moles in positons 9, 10, 11, and 14 to hide, but you’ll also make a mole
appear at position 6. Thus ending up in the next configuration.
If you then hit the mole at position 2, then all of the moles at positions 1, 2, and 6 will hide;
but a new one in position 3 will appear. There is no use of hitting empty holes, as nothing
in the board will change. You may assume that all puzzles have a solution.
Your task is to write a computer program which, given an initial board configuration, finds
ashortest sequence of moles that you can hit in order to empty the board.
There might be several correct solutions with the same optimal length, finding any of them
will be enough. Your answer should be given as a sequence of numbers with the correct
order of moles to “whack”, each separated by a single space.
Example
Find one of the shortest sequences of moles you have to hit in order to clear the board if
starting from the configuration with moles at positions 1, 2, 4, 8, 9, 10, 11, and 14.
Discussion: This is the same configuration of moles as given in the first illustration above.
After hitting moles at positions 10 and 2, you’ll end up in the following configuration.
At this point, a single hit to the mole at position 4 will clear the board.
Answer: 10 2 4
Attempts: 2 out of Infinity
Coursework uses your best attempt for grading.
Final marks: 9 / 9 (100.0%)
分析:
- 其实题目就是问我们怎么样敲地鼠才能使得全部地鼠都躲起来
- 注意有地鼠才能敲,敲完之后该位置和四周位置地鼠状态会相反(躲起来的地鼠会站起来,站起来的地鼠会躲起来)
- 直接记录4*4矩阵状态,然后一路BFS出结果
1 | import java.util.HashSet; |
优化: 由于只用了十六个数,所以其实可以用二进制进行压缩
DFS
DFS模板
1 | void dfs(答案,搜索层数,其他参数){ |
选数
题目描述
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
输入描述
键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)
输出描述
屏幕输出,格式为:
一个整数(满足条件的种数)。
1 | Input |
1 | public class 选数 { |
全排列问题
题目描述
输出自然数 1 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 n。1≤n≤9
输出格式
由 1∼n 组成的所有不重复的数字序列,每行一个序列。
每个数字保留 5个场宽。
输入 #1
1 | 3 |
输出 #1
1 | 1 2 3 |
1 | import java.util.Scanner; |
八皇后问题
题目描述
一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3个解。最后一行是解的总个数。
输入格式
一行一个正整数 n,表示棋盘是 n×n 大小的。
输出格式
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
输入
1 | 6 |
输出
1 | 2 4 6 1 3 5 |
1 | public class 八皇后 { |
迷宫
题目背景
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
输入格式
第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。(1≤N,M≤5)
输出格式
给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。
输入
1 | 2 2 1 |
输出
1 | 1 |
1 | public class 迷宫 { |
单词方阵
题目描述
给一n×n的字母方阵,内可能蕴含多个“yizhong
”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用*
代替,以突出显示单词。例如:
1 | 输入: |
输入格式
第一行输入一个数n。(7≤n≤100)。
第二行开始输入n×n的字母矩阵。
输出格式
突出显示单词的n×n矩阵。
输入
1 | 8 |
输出
1 | *yizhong |
1 | /*这道题是一个DFS的题目,从八向搜索。可以设置一个八向的常量数组,搜索每一个方向,如果满足条件就递归,否则结束递归。当搜索到第7个单词‘g’时,用vis保存路径,此次DFS也就结束了。 |
单词接龙
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastbeast和astonishastonish,如果接成一条龙则变为beastonishbeastonish,另外相邻的两部分不能存在包含关系,例如atat 和 atideatide 间不能相连。
输入格式
输入的第一行为一个单独的整数n(n≤20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式
只需输出以此字母开头的最长的“龙”的长度
输入 #1
1 | 5 |
输出 #1
1 | 23 |
说明/提示
(连成的“龙”为atoucheatactactouchoose)
1 | /* |
加分二叉树
题目描述
设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第ii个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。
若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;
(1)tree的最高加分
(2)tree的前序遍历
输入格式
第1行:1个整数n(n<30),为节点个数。
第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。
输出格式
第1行:1个整数,为最高加分(Ans ≤4,000,000,000)。
第2行:n个用空格隔开的整数,为该树的前序遍历。
输入
1 | 5 |
输出
1 | 145 |
1 | /* |
数字三角形(杨辉三角形)
Problem
有这么一个游戏:
写出一个1至N 的排列ai,然后每次将相邻两个数相加,构成新的序列,再对新序列进行这样的操作,显然每次构成的序列都比上一次的序列长度少1,直到只剩下一个数字位置。下面是一个例子:
3,1,2,4
4,3,6
7,9
16
最后得到16这样一个数字。
现在想要倒着玩这样一个游戏,如果知道N,知道最后得到的数字的大小sum,请你求出最初序列ai,为1至N的一个排列。若答案有多种可能,则输出最小的那一个。
输入格式
两个正整数n,sum。对于100%的数据,n≤12,sum≤12345。
输出格式
输出包括1行,为最小的那个答案。
当无解的时候,请什么也不输出。(好奇葩啊)
输入 #1
1 | 4 16 |
输出 #1
1 | 3 1 2 4 |
1 | /*假设一个排列数字用a,b,c,d....代替,那么它最终的和是有规律的: |
滑雪
题目描述
Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
1 | 1 2 3 4 5 |
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 24-17-16-1(从 24 开始,在 1结束)。当然 25-24-23-…-3-2-1 更长。事实上,这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 R 和列数 C。下面是 R行,每行有 C 个数,代表高度(两个数字之间用 1 个空格间隔)。对于 100% 的数据,1≤R,C≤100。
输出格式
输出区域中最长滑坡的长度。
输入 #1
1 | 5 5 |
输出 #1
1 | 25 |
1 |
|
吃奶酪
题目描述
房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 (0,0) 点处。
输入格式
第一行一个正整数 n。1≤n≤15。
接下来每行 2 个实数,表示第i块奶酪的坐标。
输出格式
一个数,表示要跑的最少距离,保留 2 位小数。
输入 #1
1 | 4 |
输出 #1
1 | 7.41 |
1 | //只能得90分,满分需要进行状态压缩 |
数独
输入: 一个未填的数独
1 | 8 0 0 0 0 0 0 0 0 |
输出: 填好的数独
1 | 8 1 2 7 5 3 6 4 9 |
1 |
|
靶型数独
Problem
比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和
总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为 2829。游戏规定,将以总分数的高低决出胜负。
输入格式
一共 9 行。每行 9 个整数(每个数都在 0∼9 的范围内),表示一个尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格隔开。对于 100% 的数据,数独中非 0 数的个数不少于 24。
输出格式
输出共 1 行。输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出整数 -1。
输入 #1
1 | 7 0 0 9 0 0 0 0 1 |
输出 #1
1 | 2829 |
输入 #2
1 | 0 0 0 7 0 2 4 5 3 |
输出 #2
1 | 2852 |
1 | //整体思路就是从已知数字最多的一行开始搜索 |
挖地雷
题目描述
在一个地图上有N个地窖(N≤20),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径。当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。
输入格式
有若干行。第1行只有一个数字,表示地窖的个数N。第2行有N个数,分别表示每个地窖中的地雷个数。第33行至第N+1行表示地窖之间的连接情况:第3行有n-1个数(0或1),表示第一个地窖至第2个、第3个、…、第n个地窖有否路径连接。如第3行为11000…0,则表示第1个地窖至第2个地窖有路径,至第3个地窖有路径,至第4个地窖、第5个、…、第n个地窖没有路径。第4行有n−2个数,表示第二个地窖至第3个、第4个、…、第n个地窖有否路径连接。… …第n+1行有1个数,表示第n−1个地窖至第n个地窖有否路径连接。(为0表示没有路径,为1表示有路径)。
输出格式
有两行第一行表示挖得最多地雷时的挖地雷的顺序,各地窖序号间以一个空格分隔,不得有多余的空格。第二行只有一个数,表示能挖到的最多地雷数。
输入
1 | 15 |
输出
1 | 11 3 4 5 |
1 |
|