题意简述:矩阵中有的点不能走,你每次可从四个方向走,至少走一步,最多走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";
}

  

最新文章

  1. [Django]用户权限学习系列之权限管理界面实现
  2. github常用操作
  3. SQL数据库基础(二)
  4. cocos2d-x的环境的搭建
  5. VS2010数据库连接问题
  6. 【python】元组的插入
  7. 数据结构与算法javascript描述
  8. RedHat安装GCC问题-解决依赖问题
  9. Linux主要发行版本介绍
  10. hdu oj1102 Constructing Roads(最小生成树)
  11. 【easy】437. Path Sum III 二叉树任意起始区间和
  12. 用ttBulkCp把excel中的数据导入到timesten数据库中
  13. jquery复制图片
  14. Linux命令行文本工具
  15. C++ error LNK2001
  16. 自建mail服务器之二:hmailserver
  17. 在 Ubuntu 13.10 安装 PyCharm 3.0.1 &amp; Oracle JDK
  18. 工具篇-大数据组件的一些快捷Shell操作
  19. cogs 547:[HAOI2011] 防线修建
  20. 软工2017第四周作业结对编程——个人psp

热门文章

  1. nmap详解之选项说明
  2. MYSQL-innobackupex备份脚本
  3. CUDA学习(三)之使用GPU进行两个数组相加
  4. 安装Mysql时提示尚未安装Python 解决方案
  5. 关于ThinkPHP在Nginx服务器下因PATH_INFO出错的解决方法
  6. pytorch之 CNN
  7. mysql ---- Host &#39;&#39; is not allowed to connect to this MySQL server
  8. 论文《A Generative Entity-Mention Model for Linking Entities with Knowledge Base》
  9. shell 颜色输出
  10. php 安装 pdo_mysql