[ABC317E] Avoid Eye Contact

CJ_Fu · 2023-08-27 10:43:51 · 题解

E 题现在水得离谱。

题目链接

洛谷

AtCoder

题目大意

给你一个 H 行 W 列的网格 A，其中 A_{i,j} 是以下字符的一种：

• .：可以正常到达的区域。
• #：障碍，无法到达。
• >、^、v、<：表示这里有一个人，他视线的方向是右/上/下/左，定义他的视线范围为从他本身开始到他视线方向的第一个障碍物（#、边界或另一个人）。
• S：起点，保证不在视线范围内。
• G：终点，保证不在视线范围内。

Naohiro 从起点出发，每次可以向上下左右四个方向中走一格，求 Naohiro 到达终点且不经过视线范围的最短距离，若无法到达输出 -1。

思路分析

应该很容易想到这是广搜板子吧。

首先预处理出所有视线范围，然后把人和视线范围都看成障碍，然后以起点跑 BFS，就求出了起点到终点的最短距离。

预处理复杂度貌似是立方级别的？其实不然。考虑最劣的情况：最外围一圈站满了向内看的人，这时的人数是 O(H+W) 级的，而遍历视线范围的复杂度是 O(H)/O(W) 级的，所以总复杂度仍然是平方级的。

时间复杂度 O(HW)，常数巨大，但是不加优化都只跑了两百多毫秒，因为预处理的巨大常数基本上跑不满。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[2003][2003];
const int wall=1;
const int see=-1;
const int pass=0;
const int L=2;
const int R=5;
const int U=3;
const int D=4;
int sx,sy,ex,ey;
queue<pair<int,int> >q;
#define x first
#define y second
int dxl[]={0,0,1,-1};
int dyl[]={1,-1,0,0};
int vis[2003][2003];
signed main(){
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            a[i][j]=wall;
        }
    }// 先全部初始化为障碍，判断边界更方便
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='.') a[i][j]=pass;
            else if(ch=='<') a[i][j]=L;
            else if(ch=='>') a[i][j]=R;
            else if(ch=='^') a[i][j]=U;
            else if(ch=='v') a[i][j]=D;
            else if(ch=='S') a[sx=i][sy=j]=pass;
            else if(ch=='G') a[ex=i][ey=j]=pass;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==L){
                int ny=j-1;
                while(a[i][ny]==pass||a[i][ny]==see) a[i][ny]=see,ny--;
            }else 
            if(a[i][j]==R){
                int ny=j+1;
                while(a[i][ny]==pass||a[i][ny]==see) a[i][ny]=see,ny++;
            }else 
            if(a[i][j]==U){
                int nx=i-1;
                while(a[nx][j]==pass||a[nx][j]==see) a[nx][j]=see,nx--;
            }else 
            if(a[i][j]==D){
                int nx=i+1;
                while(a[nx][j]==pass||a[nx][j]==see) a[nx][j]=see,nx++;
            }
        }
    }// 预处理视线范围
    q.push({sx,sy}); vis[sx][sy]=1;
    while(!q.empty()){
        int nx=q.front().x,ny=q.front().y;
        q.pop();
        for(int i=0;i<4;i++){
            int Nx=nx+dxl[i],Ny=ny+dyl[i];
            if(vis[Nx][Ny]||a[Nx][Ny]!=pass) continue;
            vis[Nx][Ny]=vis[nx][ny]+1;
            q.push({Nx,Ny});
        }
    }// BFS
    cout<<(vis[ex][ey]?vis[ex][ey]-1:-1);
}