企业官网建设流程全解析

小红的皇后

时间限制：3 秒
空间限制：256 MB

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定一个n × m n \times mn×m的棋盘，部分格子为障碍物（'*'），其余为空格（'.'）。小红控制一枚皇后，初始位于左上角( 1 , 1 ) (1, 1)(1,1)，目标是移动到右下角( n , m ) (n, m)(n,m)。皇后一次移动可以选择下列三种方式之一，并沿选定方向前进任意正整数步：

• 向右：( x , y ) → ( x , y + k ) (x, y) \to (x, y + k)(x,y)→(x,y+k)；
• 向下：( x , y ) → ( x + k , y ) (x, y) \to (x + k, y)(x,y)→(x+k,y)；
• 向右下：( x , y ) → ( x + k , y + k ) (x, y) \to (x + k, y + k)(x,y)→(x+k,y+k)；

其中k ≥ 1 k \ge 1k≥1，并且移动路径上不得出现障碍物。

求皇后从左上角移动到右下角需要的最少步数；若无法到达，输出− 1 -1−1。

输入描述

第一行输入两个整数n , m ( 1 ≤ n , m ≤ 2000 ) n, m\ (1 \le n, m \le 2000)n,m(1≤n,m≤2000)。

接下来n nn行，每行一个长度为m mm的字符串，字符集为'.'与'*'，描述棋盘。保证左上角与右下角均为'.'。

输出描述

若无法到达，输出-1；否则输出最少步数。

示例 1

输入：

3 3 ... .*. .*.

输出：

-1

示例 2

输入：

3 4 .... **.* ....

输出：

2

解题思路

本题是棋盘上带障碍的皇后最短路问题。皇后每次可以向右、下、右下三个方向移动任意正整数步，且移动路径上不能有障碍。需要求出从左上角到右下角的最少步数，若无法到达则输出-1。

由于移动方向固定且步数可任意，可以利用动态规划思想，在遍历棋盘时维护三个方向上的最小步数状态，实现线性时间复杂度。

1. 问题等价转化

• 棋盘大小为n × m，皇后起始于(1,1)，目标(n,m)。
• 三个移动方向分别为：
  • 向右：(x, y + k)
  • 向下：(x + k, y)
  • 向右下：(x + k, y + k)
    其中k ≥ 1，且移动路径上不能经过障碍。
• 要求最少的移动步数。

2. 动态规划状态设计

• 定义三个数组：

  • rb[i]：表示从起点到达第i行某个格子的最少步数，且该格子可以继续向右移动（即当前行可达的最小步数）。
  • cb[j]：表示从起点到达第j列某个格子的最少步数，且可以继续向下移动。
  • db[id]：表示从起点到达某条右下对角线上某个格子的最少步数，且可以继续沿对角线移动。

  对角线索引可通过id = (i - j) + (m - 1)唯一映射。

• 初始时，所有数组值为INF，起点(0,0)步数为0。

3. 遍历与状态转移

按行从左到右遍历整个棋盘：

• 遇到障碍'*'：
  将当前格所在行、列、对角线的状态全部重置为INF，因为障碍会阻断该方向的连续移动。

• 遇到空格'.'：
  设当前格子为(i, j)。
  计算到达该格子的最少步数：

  best = min(rb[i], cb[j], db[id]) cur = (best == INF ? INF : best + 1)

  这里best表示从某个方向到达当前格前一步的最小步数，由于需要一次新的移动（转向或首次进入该方向），所以cur = best + 1。对于起点(0,0)，cur = 0。

  然后用cur更新三个状态：

  rb[i] = min(rb[i], cur) cb[j] = min(cb[j], cur) db[id] = min(db[id], cur)

  这样，后续格子在沿同一方向移动时，可以直接继承较小的步数，而不需要额外加步数。

• 记录答案：当遍历到右下角(n-1, m-1)时，其cur即为最少步数。

4. 复杂度分析

• 时间复杂度：每个格子被访问一次，操作常数次，总复杂度O(n·m)，对于n, m ≤ 2000完全可行。
• 空间复杂度：需要存储棋盘和三个方向数组，O(n·m + n + m + n+m)，实际可接受。

总结

利用三个方向状态数组模拟皇后沿固定方向的连续移动特性，通过一次遍历实现动态规划。遇到障碍重置状态，正确维护了“同一方向连续移动步数不增加，改变方向步数加一”的最优性质。最终右下角的状态即为答案。

解题思路

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e9;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cin>>n>>m;vector<string>g(n);for(ll i=0;i<n;i++)cin>>g[i];vector<ll>rb(n,INF);vector<ll>cb(m,INF);vector<ll>db(n+m+5,INF);ll ans=INF;for(ll i=0;i<n;i++){rb[i]=INF;for(ll j=0;j<m;j++){ll id=(i-j)+(m-1);if(g[i][j]=='*'){rb[i]=INF;cb[j]=INF;db[id]=INF;continue;}ll cur;if(i==0&&j==0)cur=0;else{ll best=min(rb[i],min(cb[j],db[id]));cur=(best>=INF?INF:best+1);}if(cur<rb[i])rb[i]=cur;if(cur<cb[j])cb[j]=cur;if(cur<db[id])db[id]=cur;if(i==n-1&&j==m-1)ans=cur;}}if(ans>=INF)cout<<-1<<"\n";elsecout<<ans<<"\n";return0;}