网格迷宫中的最小转弯次数问题

题目描述

在一个无限大的二维网格迷宫中，有若干障碍格点。起点为 (sx, sy)，可以向四个方向移动，遇到障碍会停止。移动本身不花费代价，但每次左转或右转90°需要花费1点代价。给定若干出口坐标，求从起点到每个出口的最小转弯次数。

输入格式

• 第一行：4个整数 n, m, sx, sy，分别表示障碍数量、出口数量、起点坐标
• 接下来 n 行：每行2个整数 (x, y) 表示障碍坐标
• 接下来 m 行：每行2个整数 (tx, ty) 表示出口坐标

输出格式

• m 行：每行一个整数，表示到达对应出口的最小移动代价

解题思路

关键观察

1. 移动特性：沿着一个方向可以一直移动直到遇到障碍，这个过程不花费代价
2. 代价来源：只有在改变方向时才需要花费代价（每次转弯花费1）
3. 状态表示：需要记录当前位置和当前朝向

算法选择：0-1 BFS

由于边权只有0和1，可以使用双端队列BFS：

• 权值为0的边插入队首
• 权值为1的边插入队尾

核心技巧：双倍点建模

为了处理方向信息，我们为每个物理位置创建两个逻辑点：

• 水平点 i：表示在该位置且当前朝向为水平方向（左/右）
• 垂直点 i + top：表示在该位置且当前朝向为垂直方向（上/下）

建图策略

1. 收集关键点：

   • 起点
   • 所有障碍周围的点
   • 所有出口

2. 同行连接：在同一行且相邻无障碍的点之间建立权值为0的水平边

3. 同列连接：在同一列且相邻无障碍的点之间建立权值为0的垂直边

4. 方向切换：在同一位置的水平和垂直方向之间建立权值为1的切换边

复杂度分析

• 时间复杂度：$O((n + m) \log(n + m))$，主要来自排序和0-1 BFS
• 空间复杂度：$O(n + m)$，存储关键点和图结构

代码实现（码风猥琐，常数极大）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1600005;
const ll inf=1e18;

int n,t,sx,sy,top;
set<pair<int,int> > blk;  // 存储所有障碍物坐标
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};  // 四个方向：下、右、上、左
pair<int,int> a0[MAXN],ax[MAXN],ay[MAXN];  // 存储所有关键点
int b[MAXN][4];  // b[i][k]表示点i在k方向是否有障碍
map<pair<int,int>,int> id;  // 坐标到索引的映射

vector<pair<int,int> > adj[MAXN*2];  // 邻接表，存储图
ll d[MAXN*2];  // 最短距离数组

// 按y坐标排序的比较函数
bool cmpy(pair<int,int> a,pair<int,int> b){
    if(a.second!=b.second) return a.second<b.second;
    return a.first<b.first;
}

int q[MAXN*2];  // 双端队列数组
void bfs(){
    for(int i=1;i<=2*top;i++) d[i]=inf;  // 初始化距离为无穷大
    int l=top,r=top-1;  // 双端队列的左右指针
    
    // 起点有两个状态：水平方向和垂直方向
    int u=id[make_pair(sx,sy)];
    d[u]=1;  // 水平方向起点
    q[++r]=u;
    u+=top;
    d[u]=1;  // 垂直方向起点
    q[++r]=u;
    
    // 0-1 BFS：权值为0的插队首，权值为1的插队尾
    while(l<=r){
        u=q[l++];
        for(auto e:adj[u]){
            int v=e.first,w=e.second;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(w==0) q[--l]=v;  // 权值为0，插队首
                else q[++r]=v;      // 权值为1，插队尾
            }
        }
    }
}

pair<int,int> qt[MAXN];  // 存储所有出口坐标
int main(){
    scanf("%d%d%d%d",&n,&t,&sx,&sy);
    a0[++top]=make_pair(sx,sy);  // 加入起点
    
    // 读入障碍物
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        blk.insert(make_pair(x,y));
    }
    
    // 收集所有关键点：障碍物周围的点
    // 因为只能在障碍物前停下，所以关键点包括所有障碍物周围的非障碍点
    for(auto it:blk){
        int x=it.first,y=it.second;
        for(int k=0;k<4;k++){
            int x1=x+dx[k],y1=y+dy[k];
            if(!blk.count(make_pair(x1,y1))){
                a0[++top]=make_pair(x1,y1);
            }
        }
    }
    
    // 读入出口并加入关键点
    for(int i=1;i<=t;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        qt[i]=make_pair(x,y);
        a0[++top]=qt[i];
    }
    
    // 去重并排序关键点
    sort(a0+1,a0+top+1);
    top=unique(a0+1,a0+top+1)-a0-1;
    memcpy(ax,a0,sizeof(a0));  // 保存按x排序的结果
    
    // 建立坐标到索引的映射，并记录每个点四个方向的障碍情况
    for(int i=1;i<=top;i++){
        id[a0[i]]=i;
        int x=a0[i].first,y=a0[i].second;
        for(int k=0;k<4;k++){
            int x1=x+dx[k],y1=y+dy[k];
            if(blk.count(make_pair(x1,y1))) b[i][k]=1;
        }
    }
    
    // 按y坐标排序
    sort(a0+1,a0+top+1,cmpy);
    memcpy(ay,a0,sizeof(a0));
    
    // 第一步：建立水平连接（同一行相邻点的连接）
    // dir[i][k]表示点i在k方向上的下一个点
    int dir[MAXN][4]={0};
    int last=1;
    for(int i=1;i<=top;i++){
        // 找到同一行的连续段
        if(i<top&&ax[i].first==ax[i+1].first) continue;
        // 对同一行内的相邻点建立连接
        for(int k=last+1;k<=i;k++){
            int u=k,v=k-1;
            // 如果两个点之间没有障碍，则建立双向连接
            if(b[u][3]||b[v][1]) continue;  // u不能向左或v不能向右
            dir[u][3]=v;  // u向左连接到v
            dir[v][1]=u;  // v向右连接到u
        }
        last=i+1;
    }
    
    // 第二步：建立垂直连接（同一列相邻点的连接）
    last=1;
    for(int i=1;i<=top;i++){
        // 找到同一列的连续段
        if(i<top&&ay[i].second==ay[i+1].second) continue;
        // 对同一列内的相邻点建立连接
        for(int k=last+1;k<=i;k++){
            int u=id[ay[k]],v=id[ay[k-1]];
            // 如果两个点之间没有障碍，则建立双向连接
            if(b[u][2]||b[v][0]) continue;  // u不能向下或v不能向上
            dir[u][2]=v;  // u向下连接到v
            dir[v][0]=u;  // v向上连接到u
        }
        last=i+1;
    }
    
    // 第三步：建立图结构
    // 使用双倍点：i表示水平状态，i+top表示垂直状态
    for(int i=1;i<=top;i++){
        int x=ax[i].first,y=ax[i].second;
        for(int k=0;k<4;k++){
            // 添加同一方向上的移动边（权值为0）
            if(dir[i][k]){
                if(k%2) // 水平方向（右、左）
                    adj[i+top].push_back(make_pair(dir[i][k]+top,0));
                else // 垂直方向（下、上）
                    adj[i].push_back(make_pair(dir[i][k],0));
            }
            
            // 检查是否需要添加方向切换边
            int x1=x+dx[k],y1=y+dy[k];
            if(!blk.count(make_pair(x1,y1))) continue;
            
            // 添加方向切换边（权值为1）
            if(k%2) // 从垂直状态切换到水平状态
                adj[i+top].push_back(make_pair(i,1));
            else // 从水平状态切换到垂直状态
                adj[i].push_back(make_pair(i+top,1));
        }
    }
    
    // 执行0-1 BFS求解最短路径
    bfs();
    
    // 输出每个出口的结果
    for(int i=1;i<=t;i++){
        // 如果出口就是起点，代价为0
        if(qt[i].first==sx&&qt[i].second==sy){
            printf("0\n");
            continue;
        }
        int u=id[qt[i]];
        // 取水平状态和垂直状态的最小值
        ll ans=min(d[u],d[u+top]);
        if(ans==inf) printf("-1\n");
        else printf("%lld\n",ans);
    }
    
    return 0;
}

完结撒花

后记：

aha上的AC代码（卡常）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1600005;
const ll inf=1e18;

// 快读
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

// 快写
inline void write(ll x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int n,t,sx,sy,top;
set<pair<int,int> > blk;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
pair<int,int> a0[MAXN],ax[MAXN],ay[MAXN];
int b[MAXN][4];
map<pair<int,int>,int> id;

vector<pair<int,int> > adj[MAXN*2];
ll d[MAXN*2];

bool cmpy(pair<int,int> a,pair<int,int> b){
    if(a.second!=b.second) return a.second<b.second;
    return a.first<b.first;
}

int q[MAXN*2];
void bfs(){
    for(int i=1;i<=2*top;i++) d[i]=inf;
    int l=top,r=top-1;
    
    int u=id[make_pair(sx,sy)];
    d[u]=1;
    q[++r]=u;
    u+=top;
    d[u]=1;
    q[++r]=u;
    
    while(l<=r){
        u=q[l++];
        for(auto e:adj[u]){
            int v=e.first,w=e.second;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(w==0) q[--l]=v;
                else q[++r]=v;
            }
        }
    }
}

pair<int,int> qt[MAXN];
int main(){
    // 使用快读替换scanf
    n=read(); t=read(); sx=read(); sy=read();
    a0[++top]=make_pair(sx,sy);
    
    for(int i=1;i<=n;i++){
        int x=read(), y=read();
        blk.insert(make_pair(x,y));
    }
    
    for(auto it:blk){
        int x=it.first,y=it.second;
        for(int k=0;k<4;k++){
            int x1=x+dx[k],y1=y+dy[k];
            if(!blk.count(make_pair(x1,y1))){
                a0[++top]=make_pair(x1,y1);
            }
        }
    }
    
    for(int i=1;i<=t;i++){
        int x=read(), y=read();
        qt[i]=make_pair(x,y);
        a0[++top]=qt[i];
    }
    
    sort(a0+1,a0+top+1);
    top=unique(a0+1,a0+top+1)-a0-1;
    memcpy(ax,a0,sizeof(a0));
    for(int i=1;i<=top;i++){
        id[a0[i]]=i;
        int x=a0[i].first,y=a0[i].second;
        for(int k=0;k<4;k++){
            int x1=x+dx[k],y1=y+dy[k];
            if(blk.count(make_pair(x1,y1))) b[i][k]=1;
        }
    }
    
    sort(a0+1,a0+top+1,cmpy);
    memcpy(ay,a0,sizeof(a0));
    
    int dir[MAXN][4]={0};
    int last=1;
    for(int i=1;i<=top;i++){
        if(i<top&&ax[i].first==ax[i+1].first) continue;
        for(int k=last+1;k<=i;k++){
            int u=k,v=k-1;
            if(b[u][3]||b[v][1]) continue;
            dir[u][3]=v;
            dir[v][1]=u;
        }
        last=i+1;
    }
    
    last=1;
    for(int i=1;i<=top;i++){
        if(i<top&&ay[i].second==ay[i+1].second) continue;
        for(int k=last+1;k<=i;k++){
            int u=id[ay[k]],v=id[ay[k-1]];
            if(b[u][2]||b[v][0]) continue;
            dir[u][2]=v;
            dir[v][0]=u;
        }
        last=i+1;
    }
    
    for(int i=1;i<=top;i++){
        int x=ax[i].first,y=ax[i].second;
        for(int k=0;k<4;k++){
            if(dir[i][k]){
                if(k%2) adj[i+top].push_back(make_pair(dir[i][k]+top,0));
                else adj[i].push_back(make_pair(dir[i][k],0));
            }
            
            int x1=x+dx[k],y1=y+dy[k];
            if(!blk.count(make_pair(x1,y1))) continue;
            
            if(k%2) adj[i+top].push_back(make_pair(i,1));
            else adj[i].push_back(make_pair(i+top,1));
        }
    }
    
    bfs();
    
    for(int i=1;i<=t;i++){
        if(qt[i].first==sx&&qt[i].second==sy){
            putchar('0');
            putchar('\n');
            continue;
        }
        int u=id[qt[i]];
        ll ans=min(d[u],d[u+top]);
        if(ans==inf) {
            putchar('-');
            putchar('1');
            putchar('\n');
        }
        else {
            write(ans);
            putchar('\n');
        }
    }
    
    return 0;
}