牛客每日一题小红的皇后（bfs）-北京尧图网络

题目链接小红的皇后_牛客题霸_牛客网题目大意在一个n*m的网格上有若干障碍物其中有三种走法每种算一步∙ 向右(x,y)→(x,yk)∙ 向下(x,y)→(xk,y)∙ 向右下(x,y)→(xk,yk)其中 k≥1并且移动路径上不得出现障碍物。求从11到n,m)的最小移动步数如果不能到达输出-1题目思路由于让我们求最小移动步数并且每一步移动代价相同即最短路问题我们可以用bfs求解.朴素 BFS 的问题如果皇后每走一步都枚举所有可能的k1,2,3,...最坏情况复杂度 O(nm × max(n,m))会超时。优化思路利用 BFS 的层次性每个格子第一次被访问时步数一定是最少的。所以每个格子只需要入队一次从当前格子出发沿三个方向一直走到头途中遇到未访问的格子就入队遇到更优解或障碍物就停止此时对于每走一步都枚举所有可能的k1,2,3,...降到常数级别代码如下#include bits/stdc.h using namespace std; using in128 __int128_t; #define int long long bool in_bound(int x,int y,int n,int m){ return 1 x x n 1 y y m; } int bfs(int n,int m,vectorstringgrid){ vectorvectorint dist(n 1, vectorint(m 1, -1)); queuepairint, int q; q.push({1,1}); dist[1][1] 0; int dx[] {0, 1, 1}; int dy[] {1, 0, 1}; pairint, int u; while(!q.empty()){ u q.front(); q.pop(); int x u.first; int y u.second; int current_dist dist[x][y]; if(xnym){ return current_dist; } for (int dir 0; dir 3; dir) { int k 1; while(true){ int nx x dx[dir] * k; int ny y dy[dir] * k; if(!in_bound(nx,ny,n,m)||grid[nx][ny]!.){ break; } if(dist[nx][ny]-1){ dist[nx][ny] current_dist 1; q.push({nx, ny}); }else if(dist[nx][ny]current_dist) { // 如果已经有更优解提前终止 break; } k; } } } return -1; } void solve() { int n, m; cin n m; vectorstring grid(n 1); for (int i 1; i n;i){ cin grid[i]; grid[i] grid[i]; } cout bfs(n, m, grid) endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T 1; //cin T; while (T--) { solve(); } return 0; }

牛客每日一题小红的皇后（bfs）

相关推荐

【MySQL】PIPES_AS_CONCAT-性能影响分析验证报告

模型推理把 16G 内存吃满：机器学习入门教我单例加载后内存降了 70%

2026年降AI率工具怎么选？6款实测对比

更多资讯

电工证图片打印怎么搞？官方报名入口全解析，别白交培训费

初级电工证几级好考过网上查询方法及备考全攻略

电工证重新培训费用怎么报名？实操考试心里没底怕挂科怎么办

如何识别电工证的真伪行业前景与薪资待遇

低学历也能考电工证？考电工证要学哪些理论良心建议全在这

成都人才电工证报名怎么考？证书过期了不知道怎么复审延期？考前押题帮你稳过！

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？