小红的皇后
时间限制：3 秒 空间限制：256 MB
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定一个
n
×
m
n \\times m
n×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 1
k≥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
n
n 行，每行一个长度为
m
m
m 的字符串，字符集为 '.' 与 '*'，描述棋盘。保证左上角与右下角均为 '.'。
输出描述
若无法到达，输出 -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>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e9;
const ll M=1e6+10;
const ll mod=1e9+7;
int main()
{
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";
else cout<<ans<<"\\n";
return 0;
}
