关于深搜dps

哈哈,我又来了!

关于深搜dps

 

 

 但是!今天我又带来了让人开心到窒息的

                                     ————深搜dps

其实关于深搜,概念没啥可讲的,总结一句话概括就是:一直往下搜,直到满足条件的,再回来,沿着下一条路搜,直到把路全走完为止。。。。。

关于深搜dps

 

 

 关于深搜框架,我有两个:

关于深搜dps关于深搜dps

 

 

 那么,我们直接上题练练手吧:

1215:迷宫

【题目描述】

一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n×nn×n的格点组成,每个格点只有22种状态,.#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。

【输入】

第1行是测试数据的组数kk,后面跟着kk组输入。每组测试数据的第11行是一个正整数n(1≤n≤100)n(1≤n≤100),表示迷宫的规模是n×nn×n的。接下来是一个n×nn×n的矩阵,矩阵中的元素为.或者#。再接下来一行是44个整数ha,la,hb,lbha,la,hb,lb,描述A处在第haha行, 第lala列,B处在第hbhb行, 第lblb列。注意到ha,la,hb,lbha,la,hb,lb全部是从00开始计数的。

【输出】

kk行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。

【输入样例】

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

【输出样例】

YES

代码如下
关于深搜dps
关于深搜dps

 


具体思路是这样的:


首先我们看只要有解就输出,所以其实不用用回溯;


图中的小人可以向上下左右四个方向移动,所以我存两个数组,dx【4】={1,-1,0,0},dy【4】={0,0,1,-1}来表示向哪移动,如当i=1是,x=1,y=0,也就是向左移动一格;


我们把不能走的格子设为1,他所到达的地方不能是边界之外,也不能是1;


然后我们就可以愉快地深搜啦,直到搜到终点,结束!!!


关于深搜dps

 

 

 是不是有点理解了?其实我赌没理解。。。。。

再来道题吧

1212:LETTER

【题目描述】

给出一个roe×colroe×col的大写字母矩阵,一开始的位置为左上角,你可以向上下左右四个方向移动,并且不能移向曾经经过的字母。问最多可以经过几个字母。

【输入】

第一行,输入字母矩阵行数RR和列数SS,1≤R,S≤201≤R,S≤20。

接着输出RR行SS列字母矩阵。

【输出】

最多能走过的不同字母的个数。

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

6

(复制加粘贴)这是一道简单的搜索题(我信你个鬼)题目的意思是指在字母表中,向上下左右四个方向探索,如果字母重复则结束这个方向的探索。以样例为例,先从H开始探索,向上不能探索,向右继续探索,H->F,向上不能探索,向右H->F->D,再向右则F重复,向下H重复,向左F重复,所以,回溯到F,继续向下探索,

 

那么,我们就可以嘿嘿啦
关于深搜dps关于深搜dps

 

 

 就这样吧!!!再见 !!!

关于深搜dps

 

 

 

 

上一篇:X46Cr13的机械性能1.4034


下一篇:CSP2020 游记