cf877D
2024-09-04 22:49:01
题意简述:矩阵中有的点不能走,你每次可从四个方向走,至少走一步,最多走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";
}
最新文章
- [Django]用户权限学习系列之权限管理界面实现
- github常用操作
- SQL数据库基础(二)
- cocos2d-x的环境的搭建
- VS2010数据库连接问题
- 【python】元组的插入
- 数据结构与算法javascript描述
- RedHat安装GCC问题-解决依赖问题
- Linux主要发行版本介绍
- hdu oj1102 Constructing Roads(最小生成树)
- 【easy】437. Path Sum III 二叉树任意起始区间和
- 用ttBulkCp把excel中的数据导入到timesten数据库中
- jquery复制图片
- Linux命令行文本工具
- C++ error LNK2001
- 自建mail服务器之二:hmailserver
- 在 Ubuntu 13.10 安装 PyCharm 3.0.1 &; Oracle JDK
- 工具篇-大数据组件的一些快捷Shell操作
- cogs 547:[HAOI2011] 防线修建
- 软工2017第四周作业结对编程——个人psp
热门文章
- nmap详解之选项说明
- MYSQL-innobackupex备份脚本
- CUDA学习(三)之使用GPU进行两个数组相加
- 安装Mysql时提示尚未安装Python 解决方案
- 关于ThinkPHP在Nginx服务器下因PATH_INFO出错的解决方法
- pytorch之 CNN
- mysql ---- Host &#39;&#39; is not allowed to connect to this MySQL server
- 论文《A Generative Entity-Mention Model for Linking Entities with Knowledge Base》
- shell 颜色输出
- php 安装 pdo_mysql