题意简述:矩阵中有的点不能走,你每次可从四个方向走,至少走一步,最多走k步(不能横跨那些不能走的格子),问从(sx,sy)走到(tx,ty)的最短时间是多少?
题意:利用set来加速bfs的过程,原理是一个点一旦走过就不需要再去走了,具体看代码
#include <bits/stdc++.h> using namespace std; const int N = 1002; bool G[N][N]; int n, m, k, d[N][N]; set<int> xs[N], ys[N]; void clear_rem(vector<pair<int,int> > &rem){ for(auto p : rem){ xs[p.first].erase(p.second); ys[p.second].erase(p.first); } rem.clear(); } void bfs(int sx, int sy){ xs[sx].erase(sy); ys[sy].erase(sx); queue<pair<int,int> > q; q.push({sx,sy}); d[sx][sy]=0; while(!q.empty()){ pair<int,int> u=q.front(); q.pop(); int x = u.first, y=u.second; vector<pair<int,int> > rem; for(auto it=xs[x].lower_bound(y); it!=xs[x].end(); it++){ if(*it-k>y || !G[x][*it])break; rem.push_back({x,*it}); q.push({x,*it}); d[x][*it]=d[x][y]+1; } clear_rem(rem); for(auto it=ys[y].lower_bound(x); it!=ys[y].end(); it++){ if(*it-k>x || !G[*it][y])break; rem.push_back({*it,y}); q.push({*it,y}); d[*it][y]=d[x][y]+1; } clear_rem(rem); auto it=xs[x].lower_bound(y); if(it!=xs[x].begin()){ it--; while(1){ if(y-*it>k || !G[x][*it])break; rem.push_back({x,*it}); q.push({x,*it}); d[x][*it]=d[x][y]+1; if(it==xs[x].begin())break; it--; } } clear_rem(rem); it=ys[y].lower_bound(x); if(it!=ys[y].begin()){ it--; while(1){ if(x-*it>k || !G[*it][y])break; rem.push_back({*it,y}); q.push({*it,y}); d[*it][y]=d[x][y]+1; if(it==ys[y].begin())break; it--; } } clear_rem(rem); } } int main(){ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(d,-1,sizeof(d)); cin >> n >> m >> k; for(int x=1; x<=n; x++) for(int y=1; y<=m; y++){ char c; cin >> c; G[x][y]=c=='.'; xs[x].insert(y); ys[y].insert(x); } int X, Y; cin >> X >> Y; bfs(X,Y); cin >> X >> Y; cout << d[X][Y] << "\n"; }