G 清楚姐姐逛街(Easy Version)
题意
终点会按照固定方式移动的搜索问题，多次查询
思路
- 只要时间t是确定的，那么终点的位置就是确定的 -> 可以模拟每一时刻
- bfs维护智乃到每个点的最短距离
- 模拟每一时刻清楚姐姐的位置
- 如果该时刻大于智乃到每个点的最短距离（前提是智乃能够到达该位置）则为答案
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef long long LL;
typedef pair<int,int> pii;
const char nl = '\n';
const int N = 810;
const int M = 810;
int n,m,x,y,q;
int z[N][M],qc[N][M],dx[]={-1,1,0,0},dy[]={0,0,1,-1};
char g[N][M];
void bfs(){
queue<pair<pii,int>> q;
q.push({{x,y},0}); //储存坐标和最短距离
z[x][y] = 0; //记得要初始化原点为0
while(q.size()){
auto u = q.front();
q.pop();
for(int i = 0; i < 4; i ++){
int nx = u.X.X + dx[i];
int ny = u.X.Y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#' || z[nx][ny] != -1)continue;//出界或者不能走或者已经走过
else{
q.push({{nx,ny},u.Y+1});
z[nx][ny] = u.Y + 1; //下一个点最短距离等于当前点最短距离+1
}
}
}
}
void solve(){
cin >> n >> m >> x >> y >> q;
for(int i = 0;i < n; i ++){
for(int j = 0; j < m; j ++){
cin >> g[i][j];
}
}
memset(z,-1,sizeof z); //初始化为-1
bfs(); //维护智乃到某一的最短距离
while(q--){
bool f = 0;
int a,b;
cin >> a >> b;
int na = a,nb = b;
int t = 0;
while(t<n*m){//清楚姐姐走完全地图最多有n*m
t ++; //模拟每一时刻的动作
char c = g[na][nb];
if(c == 'L'&&g[na][nb-1]!='#')nb -= 1;//如果能走
else if(c == 'R'&&g[na][nb+1]!='#')nb += 1;
else if(c == 'U'&&g[na-1][nb]!='#')na -= 1;
else if(c == 'D'&&g[na+1][nb]!='#')na += 1;
if(t >= z[na][nb] && z[na][nb] != -1){
cout << t << nl;
f = 1;
break;
}
}
if(!f)cout << -1 << nl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}