[ABC276E] Round Trip 题解

FFTotoro · 2022-11-06 12:10:40 · 题解

前言

官方题解：本题可以使用广度优先搜索或并查集实现。

我：运用深度优先搜索加一波奇怪的剪枝通过了本题。

解法

本题可以使用深度优先搜索加上剪枝实现。

首先我们用 std::vector 来实现一个 bool 型二维数组，存储每个点是否能走。具体地，这里的“不能走”的点分为 3 类：

• 有障碍物的点；

• 已经走过过的点；

• 剪枝剪掉的点（这个在后面会详细说明）；

于是，我们就可以从起点开始，往四个方向暴搜。这时的暴搜中的 bool 数组只存储上面说的 3 类的前面 2 类点。

但是，你把暴搜的程序交上去，会发现有 7 个 TLE。

所以，我们需要对搜索进行剪枝。

对于我们走到的点，不计它的前驱（也就是上一个搜到的点），一共还有 3 个相邻的点。这时对其分类讨论一下：

• 有且仅有 2 个点是“不能走的点”：可以继续搜索，但是回溯的时候不要取消标记，即让它成为上面所述“剪枝剪掉的点”（因为它四个相邻的点只有两个是“可走的”，如果我们从除了前驱的另一个点再搜回这个点，它的下一个点必然是原先搜索过的“前驱”，继续搜索是没有意义的，所以不去标记，让别的地方搜不到它）；

• 其他情况：按照普通的点搜索即可。

这样，TLE 就被完美地解决了。

放代码：

#include<bits/stdc++.h>
using namespace std;
int h,w,sx,sy;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; // 方向数组
vector<string> s; // 地图数组
vector<vector<bool> > b; // 标记数组
bool dfs(int x,int y,int t){
  int c=0; b[x][y]=true;
  for(int i=0;i<4;i++){
    int xx=x+dx[i],yy=y+dy[i]; // 下一步可能搜到的点
    if(xx==sx&&yy==sy){
      if(t>=3){
        cout<<"Yes\n";
        return true; // 搜到了返回
      }
      else continue; // 步数不够
    }
    if(xx<0||xx>=h||yy<0||yy>=w||b[xx][yy]){c++; continue;} // 不合法方案（搜到边界或已经搜过）
    if(dfs(xx,yy,t+1))return true; // 合法方案
  }
  if(c<3)b[x][y]=false; // 需要去标记的情况
  return false;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin>>h>>w; s.resize(h);
  b.resize(h,vector<bool>(w));
  // 由于 h 和 w 不确定，所以需要开动态的 vector
  for(auto &i:s)cin>>i;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(s[i][j]=='S')sx=i,sy=j;
      else if(s[i][j]=='#')b[i][j]=true;
  if(!dfs(sx,sy,0))cout<<"No\n"; // 无解的情况
  return 0;
}