题解 P1189 【`SEARCH`】
stone_juice石汁 · · 题解
标签明示要用dfs 或bfs 。题解中也有单独用dfs 或bfs 做的。
我发现我更过分。
我两个都用了XD
为什么发新题解？
1、方法不同：因为我发现我不仅只是用了两种搜索实现简便运作，我还是第一个开两个队列，用存点和缓存机制
2、详细易懂：我自认为我的题解算是比较详细了，希望能帮到那些没看懂其他题解的OIer
当然，如果我写的不好，轻喷QWQ。如果能看得过去，也希望对大家有帮助
那么说一下我的做法：bfs 处理 + dfs 扩展 + 队列存点与缓存 + 判重剪枝 * 1
等等！先别被我标题劝退！实际上技术含量很低。
说得好像很高级，其实就是胡搞乱搞出来的
我觉得我写的算详细了。如果你有耐心读完，估计也就会做了（吧？？？）
这道题坑点倒是蛮多的，请让我一一道来
-
先说思路吧：
1、开两个队列，一个用于存点，一个用于缓存（以下简称为
q 队列与t 队列），至于这两个队列有什么不一样...往下看2、先读入整张图（必须的）。开二维
char 数组，就按输入老老实实存就行了。*读到 $的时候，把当前的坐标直接 push进 q队列。理所应当地，在传进队列后，这个 就没用了，因为之后车可能不会开回，并且我们把起始点给记住了。所以把 直接换成 .$（空位） 。**3、接下来就是一个
bfs 的过程。取光q 队列里的全部坐标，每个坐标都进行一次方向扩展。方向扩展由dfs 完成。 由于方向是固定的，通过输入给出，所以这个dfs 时间复杂度一点也不高。（其实你可以写一个循环代替dfs ，但要开多变量，麻烦。所以说这是一个很不标准的dfs XD）。4、上面提到过
bfs 负责把存储的坐标扔给dfs ，dfs 往规定方向扩展。每跑到一个符合规则的点就把这个点坐标扔给t 队列。 直到遇到X 或者 边界（我搞这个东西的时候把边界忘了于是RE 过 XD）。5、最后在处理扩展完
q 队列中的所有坐标后，把缓存在t 队列里的坐标全被扔进q 队列。6、每次操作一遍更换方向，就重复一遍3，4，5的过程。
7、最后，处理完成的答案坐标（即车可能开到的位置的坐标）全部存在
q 队列中。弹出所有坐标，把那个位置的符号改为* 。输出整张图。8、卖萌装傻庆祝
AC 所有步骤均在代码中有批注，易于各位OIer们寻找！
-
Q & A 及坑点
- 1、
Q：为什么要开两个队列，一个队列实现处理和录入不行吗？
A：当然不行。因为在
q 队列扔出数据处理后，是会引入新坐标的。毕竟队列里的坐标只能一个一个处理，不可能一下子扔完。而边扔出边引入则会引起数据混乱或无限循环。 毕竟q 队列要扔出所有的坐标啊...刚引入的坐标是不能扔出去的，要留在下一轮处理。所以这才有了缓冲队列t 。- 2、
Q：怎么实现通过输入字符串让
dfs 有针对性地扩展（只往规定方向扩展）？A：我的做法是这样的：
输入的不是字符串吗？然而我更喜欢用
N S W E 表示方向，怎么办？好说！：取每个字符串的第一个字符就可以了。
Q：那怎么把字符判断转化为扩展限制？
A：我定义了两个数组：
dx[4] = ｛0, 0, -1, 1｝
dy[4] = ｛-1, 1, 0, 0｝
这种数组应该是司空见惯了。稍微想一下，就能想到
N S W E 分别对应2，3，0，1 （下标值）。定义一个
int 变量pd ，判断一下，扔到dfs 里去就可以了。- 3、Q：这种做法不会爆时间吗？
A：不会
那是不可能滴（滑稽），你不剪枝，只能跑
30 分。而且还会爆空间，贼恐怖。但是我们可以剪枝。
观察
dfs 的过程，再来看下面这张图：星号表示待处理坐标，规定方向向北。
假设我们现在处理了黄色区块的坐标，浅蓝色区域全部都会被录入。
那么再次处理上面两个坐标就没有意义了。实际上，当数据很大的时候，这样重复处理浪费了不少时间和空间。
所以，我们直接申明一个
vis 数组（bool 型），已经看过的点就不再去管他了。于是我们就有了一个
100 分的AC 代码！ -
上代码！
#include<bits/stdc++.h> #define mian main #define QWQ puts("QWQ"); #define inf 0x3f3f3f3f #define maxn 55 using namespace std; //第一步：开队列及相关变量数组 int n, m, w;//n，m：长宽，w：方向变化数 char _map[maxn][maxn]; int pd;//pd用来记录方向以便在dfs发挥定向作用 int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};//如上文所讲 bool vis[maxn][maxn];//去重判断用 string d;//用来录入方向 queue <int> q;//存储队列 queue <int> t;//缓存队列 void dfs(int x, int y, int p)//第四步：深搜来跑单向路径，把跑过的坐标记录进缓冲队列t { int tx = x + dx[p], ty = y + dy[p]; if(_map[tx][ty] == 'X' || tx > n || tx <= 0 || ty > m || ty <= 0) return;//遇到障碍或边界就不跑了 if(vis[tx][ty]) return;//很重要的剪枝：之前处理过也不跑了，因为都是同向，跑下去也一样，能省去大量时间。 vis[tx][ty] = true; //打上标记 t.push(tx); t.push(ty); dfs(tx, ty, p); } void bfs(string dir) { while(!q.empty())//第三步：查找q中所有坐标并进行 移动 记录 缓存 操作 { int tx = q.front(); q.pop(); int ty = q.front(); q.pop(); if(dir[0] == 'N') pd = 2; else if(dir[0] == 'S') pd = 3; else if(dir[0] == 'W') pd = 0; else if(dir[0] == 'E') pd = 1;//判断一下方向。 dfs(tx, ty, pd); } memset(vis, false, sizeof(vis));//记得每次清空vis数组 while(!t.empty())//将缓冲队列t中的缓存坐标转移到q中 { q.push(t.front()); t.pop(); q.push(t.front()); t.pop(); } } int main() { cin >> n >> m; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { cin >> _map[i][j];//第二步：录入整张图 if(_map[i][j] == '*')//扫到起始点 { q.push(i); q.push(j); _map[i][j] = '.';//因为已经记录进q队列，没有再留的必要，打回原形。 } } cin >> w; for(int i = 1; i <= w; i ++)//第6步：每次读入都重复过程 { cin >> d; bfs(d); } while(!q.empty())//第7步：直接取出q中所有坐标，改符号为*并输出图 { int tx = q.front(); q.pop(); int ty = q.front(); q.pop(); _map[tx][ty] = '*'; } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) cout << _map[i][j]; cout << endl; } return 0;//第8步：QWQ }希望我的这篇题解对大家有帮助！
码子不易，各位大佬是不是应该....