ABC317_E

梦见云月 · 2023-08-27 10:22:28 · 题解

题意简述：

简单地说，就是从起点 S 走到终点 G，其中 # 是障碍物不能走，且不能走到在别人的视线中，如果可以走过去，输出步数，否则输出 -1。

思路：

这道题还是很水的，一个 bfs 就能直接过。

首先先记录一下起点的坐标和终点的坐标。

但是要注意对四个符号的判断，这部分的话只需要不断把他们视线内的东西变为 ! 即可。

以下是以 ^ 为例的代码。

if(ch[i][j]=='^'){
   int ii=i-1,jj=j;
   while((ch[ii][jj]=='.'||ch[ii][jj]=='!')&&ii>=1) 
        ch[ii--][jj]='!';
}

处理完之后，直接 bfs，我们使用队列和 pair 的组合，用 pair 来储存坐标，用偏移量来辅助移动，用二维数组 f 来储存步数，最后输出终点坐标的步数即可。

如果终点坐标的步数为零，说明无法到达，输出 -1 即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h,w,sx,sy,ex,ey;
char ch[2005][2005];
int fff[2005][2005];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs(){
    queue<pair<int,int> > q;
    q.push({sx,sy});
    while(q.size()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=1 && xx<=h && yy>=1 
                && yy<=w && !fff[xx][yy] && ch[xx][yy]!='!' 
                && ch[xx][yy]!='#' && ch[xx][yy]!='<' && ch[xx][yy]!='>'  
                &&ch[xx][yy]!='^'&&ch[xx][yy]!='v'){

                q.push({xx,yy});
                fff[xx][yy]=fff[x][y]+1;
            }
        }
    }
}
signed main(){
    cin>>h>>w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>ch[i][j];
            if(ch[i][j]=='S') 
                sx=i,sy=j; // 记录起点位置 
            if(ch[i][j]=='G') 
                ex=i,ey=j; // 记录终点位置 
        }
    }
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(ch[i][j]=='<'){
                int ii=i,jj=j-1;
                while((ch[ii][jj]=='.'||ch[ii][jj]=='!')&&jj>=1) 
                    ch[ii][jj--]='!';
            }
            else if(ch[i][j]=='>'){
                int ii=i,jj=j+1;
                while((ch[ii][jj]=='.'||ch[ii][jj]=='!')&&jj<=w) 
                    ch[ii][jj++]='!';
            }
            else if(ch[i][j]=='v'){
                int ii=i+1,jj=j;
                while((ch[ii][jj]=='.'||ch[ii][jj]=='!')&&ii<=h) 
                    ch[ii++][jj]='!';
            }
            else if(ch[i][j]=='^'){
                int ii=i-1,jj=j;
                while((ch[ii][jj]=='.'||ch[ii][jj]=='!')&&ii>=1) 
                    ch[ii--][jj]='!';
            }
        }
    }
    bfs();
    if(fff[ex][ey]!=0) 
        cout<<fff[ex][ey];
    else 
        cout<<-1;
    return 0;
}