题目链接小红的皇后_牛客题霸_牛客网题目大意在一个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; }