写在前面（可自行跳过）

• 我的解法显然不是最优的，不值得抄，毕竟我不(fei)会(chang)卡(de)常(cai)

• 请原谅我奇丑无比的博客，毕竟我不(fei)会(chang)美(de)化(cai)

一句话题意

给定一个长方形网格，求网格上每个点到一个目标点最少的拐弯次数。

下面是主要部分↓

题解

口糊

显然是个最短路。可以考虑用一个类似SPFA的算法。

一开始，把所有关键点加入队列，距离设为0，其他点距离为INF。然后进行SPFA对于每个点，向四个方向枚举直到出边界或者碰到障碍，对于每个枚举到的点，用当前点的最小次数+1更新枚举点的最小次数，然后O(1)回答。

但是我们知道SPFA是不稳定的。

可是这道题的（假的）SPFA是稳定的$n^2$。因为每次更新的增加量（也就是平时FPFA中的边权）是固定的1,所以按入对顺序排好每个点后，其答案是递增的。这保证了每个点只入队一次，点数是$n^2$的。同时因为这条性质，我的代码中有很多操作是多余的，但是太懒就没去改。

AC代码

(这道题还有个坑，就是每行末尾不能输出多余空格，但是可以在末尾输出多余空行)

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct Pair{
    int x,y;
}tmp;
int n,m,mn[2010][2010],x,y,vis[2010][2010];
char c[2010][2010];
queue<Pair>q;
void getc(char &c){
    c=getchar();
    while(c==' '||c=='\n'){
        c=getchar();
    }
}
void SP(){
    while(!q.empty()){
        tmp=q.front();
        x=tmp.x;
        y=tmp.y;
        q.pop();
        for(int i=1;x+i<=n&&c[x+i][y]!='#';i++){
            if(mn[x+i][y]>mn[x][y]+1){
                mn[x+i][y]=mn[x][y]+1;
                if(!vis[x+i][y]){
                    vis[x+i][y]=1;
                    tmp.x=x+i;
                    tmp.y=y;
                    q.push(tmp);
                }
            }
        }
        for(int i=1;x-i>=1&&c[x-i][y]!='#';i++){
            if(mn[x-i][y]>mn[x][y]+1){
                mn[x-i][y]=mn[x][y]+1;
                if(!vis[x-i][y]){
                    vis[x-i][y]=1;
                    tmp.x=x-i;
                    tmp.y=y;
                    q.push(tmp);
                }
            }
        }
        for(int i=1;y+i<=m&&c[x][y+i]!='#';i++){
            if(mn[x][y+i]>mn[x][y]+1){
                mn[x][y+i]=mn[x][y]+1;
                if(!vis[x][y+i]){
                    vis[x][y+i]=1;
                    tmp.x=x;
                    tmp.y=y+i;
                    q.push(tmp);
                }
            }
        }
        for(int i=1;y-i>=1&&c[x][y-i]!='#';i++){
            if(mn[x][y-i]>mn[x][y]+1){
                mn[x][y-i]=mn[x][y]+1;
                if(!vis[x][y-i]){
                    vis[x][y-i]=1;
                    tmp.x=x;
                    tmp.y=y-i;
                    q.push(tmp);
                }
            }
        }
        vis[x][y]=0;
    }
}
void print(int x){
    if(x>9){
        print(x/10);
    }
    putchar(x%10+'0');
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            getc(c[i][j]);
            if(c[i][j]=='+'){
                mn[i][j]=0;
                tmp.x=i;
                tmp.y=j;
                q.push(tmp);
                vis[i][j]=1;
            }else{
                mn[i][j]=INF;
            }
        }
    }
    SP();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[i][j]=='#'){
                putchar('#');
            }else{
                if(mn[i][j]>=INF){
                    putchar('X');
                }else{
                    print(mn[i][j]);
                }
            }
            if(j!=m){
                putchar(' ');
            }
        }
        puts("");
    }
    return 0;
}