自动搬运

查看原文

来自洛谷，原作者为

	stone_juice石汁 敲稀有滴物种石汁qaq

搬运于2025-08-24 21:22:15，当前版本为作者最后更新于2019-08-04 21:20:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

标签明示要用$dfs$或$bfs$。题解中也有单独用$dfs$或$bfs$做的。

我发现我更过分。

我两个都用了XD

为什么发新题解？

**1、方法不同：**因为我发现我不仅只是用了两种搜索实现简便运作，我还是第一个开两个队列，用存点和缓存机制$A$了这道题的人

**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 
  }
  

希望我的这篇题解对大家有帮助！

码子不易，各位大佬是不是应该....