本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-23 15:41:40
考场上写出了正解，但是忘加前缀和优化，大样例不是极限数据还跑得挺快的，寄成了 65。
Solution
考虑对于点 $(i,j)$ 其能直接走到哪些点。
本文仅考虑向右走的情况，其他情况本质一样。
假设 $(i,j)$ 右边第一个障碍位置是 $(i,x)$。
那么 $(i,j)$ 依次能走到：
- $(i,x-1)$。
- $(i,j+1)$。
- $(i,x-2)$。
- $(i,j+2)$。
- 以此类推。
对于上述第 $l$ 个点，$(i,j)$ 向其连接一条权值为 $l$ 的边。
直接这么建边就是对的，但是一次上述跳转，产生的新障碍可能会影响后面的其他跳转，为啥不会有问题？
因为如果一次横跳（就是上面描述的样子）之后，兜兜转转进行另一次横跳，并且和第一次横跳涉及到的节点交叉了，这种情况的答案一定不是最优的，算出的答案不会影响最优解，因为完全可以在第一次横跳的时候，在第一次横跳与第二次横跳交叉的节点直接开启第二次横跳。
按照上述建图方式会 TLE，还得优化。
注意到，$(i,j)$ 走到 $(i,j+1)$ 的权值为 $2$，走到 $(i,j+2)$ 权值为 $4$，以此类推走到 $(i,j+k)$ 权值为 $2k$。
然后 $(i,j)$ 走到 $(i,x-1)$ 的权值为 $1$，走到 $(i,x-2)$ 权值为 $3$，以此类推走到 $(i,x-k)$ 的权值为 $1+2(k-1)$。
上述若出现共同点则按照最小权值，不过直接建图最短路建出重边也无所谓。
这样优化：对于任意点 $(i,j)$ 满足 $(i,j)$ 和 $(i,j+1)$ 都不是障碍，那么 $(i,j)$ 向 $(i,j+1)$ 连一条权值为 $2$ 的双向边。
对于 $(i,j)$ 其向 $(i,x-1)$ 连一条权值为 $1$ 的边即可。
明显地上述做法可以得到最优解，并且稍微画一下或想象一下图的样子可以发现这样绝对不会让答案算小。
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
void io(){
freopen("skate.in","r",stdin);
freopen("skate.out","w",stdout);
}
const int maxn=1e3+5;
int n,m;
char s[maxn][maxn];
int r1,c1,r2,c2;
vector<pair<pii,int> > g[maxn][maxn];
int r_lstblk[maxn][maxn],r_nxtblk[maxn][maxn],c_lstblk[maxn][maxn],c_nxtblk[maxn][maxn];
bitset<maxn> vis[maxn];
int dis[maxn][maxn];
void dij(){
memset(dis,0x3f,sizeof dis);
priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > > q;
q.push(mkpr(0,mkpr(r1,c1)));
dis[r1][c1]=0;
while(!q.empty()){
auto cur=q.top().se;
q.pop();
int x=cur.fi,y=cur.se;
if(vis[x][y])continue;
vis[x][y]=1;
for(auto& v:g[x][y]){
int fx=v.fi.fi,fy=v.fi.se,w=v.se;
if(dis[fx][fy]>dis[x][y]+w){
dis[fx][fy]=dis[x][y]+w;
q.push(mkpr(dis[fx][fy],mkpr(fx,fy)));
}
}
}
if(dis[r2][c2]>1e8){
puts("-1");
return;
}
printf("%d\n",dis[r2][c2]);
}
void solve(int id_of_test){
scanf("%d%d",&n,&m);
FOR(i,1,n){
scanf("%s",s[i]+1);
}
read(r1);
read(c1);
read(r2);
read(c2);
FOR(i,1,n){
int lst=1;
FOR(j,1,m){
if(s[i][j]=='#')lst=j;
else r_lstblk[i][j]=lst;
}
lst=m;
REP(j,m,1){
if(s[i][j]=='#')lst=j;
else r_nxtblk[i][j]=lst;
}
}
FOR(j,1,m){
int lst=1;
FOR(i,1,n){
if(s[i][j]=='#')lst=i;
else c_lstblk[i][j]=lst;
}
lst=n;
REP(i,n,1){
if(s[i][j]=='#')lst=i;
else c_nxtblk[i][j]=lst;
}
}
FOR(i,1,n){
FOR(j,1,m){
if(s[i][j]=='#')continue;
if(s[i][j-1]!='#'){
g[i][j].eb(mkpr(mkpr(i,j-1),2));
}
if(s[i][j+1]!='#'){
g[i][j].eb(mkpr(mkpr(i,j+1),2));
}
if(s[i-1][j]!='#'){
g[i][j].eb(mkpr(mkpr(i-1,j),2));
}
if(s[i+1][j]!='#'){
g[i][j].eb(mkpr(mkpr(i+1,j),2));
}
}
}
FOR(i,1,n){
FOR(j,1,m){
if(s[i][j]=='#')continue;
{
int lst=c_lstblk[i][j]+1;
g[i][j].eb(mkpr(mkpr(lst,j),1));
}
{
int nxt=c_nxtblk[i][j]-1;
g[i][j].eb(mkpr(mkpr(nxt,j),1));
}
{
int lst=r_lstblk[i][j]+1;
g[i][j].eb(mkpr(mkpr(i,lst),1));
}
{
int nxt=r_nxtblk[i][j]-1;
g[i][j].eb(mkpr(mkpr(i,nxt),1));
}
}
}
dij();
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
\/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法匹配？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*\/
鲁ICP备2025150228号