Charlesss

ACM_搜索

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_最短路(14) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

全部文章 / ACM_搜索（共24篇）

2018年湘潭大学程序设计竞赛 F.maze(优先队列搜索)

题目链接：https://www.nowcoder.com/acm/contest/105/F 刚开始以为直接用bfs就可以过了，但是不用优先队列的话只能过33.3%的样例，因为有的步数花费1秒，有的花费3秒，所以需要用优先队列取出花费时间最少的点，然后用了优先队列发现过...

2018-05-03

0 447

Poj 1564 || HDU 1258 Sum It Up(dfs+技巧)

题意就是先输入n,m，然后输入m个数，问在这m个数里有多少种任意相加起来等于n的方法，并且输出这些相加的数。首先在进行dfs前我们可以把前面那些大于n的数省掉，比如说n是3，m个数为6，5，4，3，2，1，那么我们可以直接从第4个数开始进行dfs。然后在搜索到一种满足sum...

2018-03-17

0 428

Red and Black(dfs&&bfs)

题意是，一个地图，起点为'@'，求和它连着的空地有多少。很简单的搜索题，用了深搜和广搜。注意题上的数据给的是列和行，不是我们所习惯的行和列。 AC代码： #include <iostream> #include <cstdio> #include <...

2018-03-09

0 369

HDU 1035 Robot Motion(dfs)

题意就是输入n*m的地图，然后输入p，表示这个机器人从(1,p)这个点为起点，然后至于机器人怎么走应该不用解释了吧，判断的终点就是走出地图，这里我们可以稍稍的做个预处理，地图从1开始输入，那么结束条件就是到达0，n+1，m+1就行了。把字母换成数字存起来，然后每走过一个点都用走的步数标...

2018-03-08

0 353

八皇后问题(回溯)

在做这道题之前搜了一下回溯和递归的区别，递归就是一个劲的往下搜，搜到头了走不通了，再倒回来换条路继续搜，而回溯就是搜到结果以后再回头重新换个点继续重新搜。这道题是紫书上P191的一道例题，也是一道经典的回溯搜索题，题的描述就是有一个8*8的棋盘，然后...

2018-03-08

0 457

CodeForces 242C King's Path(bfs+map)

题意就是走地图，输入起点终点，然后输入某行的某些点可以走，然后问你最后能不能走到终点，能的话输出最少步数。仔细读一下题会发现地图的范围太大了，用二维数组肯定是存不下的，所以我们需要换种方法去存图，可以用结构体去存，这里我用的是map和pair，具体过程看代码吧。 AC代码： #incl...

2018-02-21

0 579

POJ 3984 迷宫问题(bfs+pair)

求最短路问题，但是需要打印路径，那么就需要把路径存下来，可以用结构体来存，这里我用的是pair。最后输出路径的时候是一个递归过程，理解不了的可以手动模拟一下，样例也不长。 AC代码： #include <iostream> #include <cstdio> ...

2018-02-20

0 487

UVA 11624 Fire!(双点bfs)

这道题就是问一个人能否逃出地图，当然不是那种简单的走地图，还有一堆火(划重点)。说下思路，这道题坑点还是比较多的，首先火源不只一处，可以有多处，那么我们就要把每处火都记录下来，然后bfs搜索前让火源全部入队，还有就是不需要逃出地图，只要跑到边界就ok。(说是双点bfs，其实就是把火和人...

2018-02-14

0 448

POJ 3126 Prime Path(bfs)

简单的bfs搜索 AC代码： #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> using ...

2018-02-14

0 511

POJ 1321 棋盘问题(dfs)

讲一下大概思路，因为题目上要求棋子不能在同一行或同一列种出现，所以我们可以按行、列来进行搜索，一行一行的搜索，然后标记搜索到的那一列，然后再往下继续搜索。结合代码看吧。 AC代码： #include <iostream> #include <cstring> ...

2018-02-14

0 488