获得更好的阅读体验

观察本题之后，发现有一个易错点：坐标可能为负。

我们知道，$\text{C++}$中数组下标必须是非负。题目中给出了$-500 \le X \le 500,-500 \le Y \le 500$的条件，所以只需要把所有的下标加上$500$，就一定能满足所有下标为非负。这样，数组大小只需要开到$1000$以上（不包括$1000$）即可。

程序的实现可以使用宽搜，因为宽搜适合处理最优解。而深搜会暴力枚举每一个点，然而这里的点是杂乱无章的，所以深搜的效率是很低的。

我们可以建立一个二维数组来保存对应位置是否有泥，同时在访问过没有泥地的地方之后就可以把这个地方标记为有泥。因为题目要求不进入泥地，而走过的路就不可能再走了，所以可以把visit和mud两个数组结合起来使用。这样做的根本原因是$\text{BFS}$不需要回溯，因此不需要重新标记。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int ex,ey,n,front=1,rear=1,dx[]={-1,0,0,1},dy[]={0,-1,1,0};//ex,ey为结束坐标，n为泥地个数，front,rear分别为队头、队尾，dx,dy为增量数组
bool mud[1001][1001];//注意下标要开到1000以上（不含）
struct node
{
    int x,y,step;
}q[1000001];//1000*1000=10^6，所以队列下标只需要开到10^6（不含）以上即可
int main()
{
    scanf("%d%d%d",&ex,&ey,&n);
    for(int i=0,a,b;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        mud[a+500][b+500]=true;//对每一个输入的坐标都要加500
    }
    q[1]=(node){500,500,0};//注意初始坐标要加500
    while(front<=rear)
    {
        node f=q[front++];
        for(int i=0;i<4;i++)
        {
            int nx=f.x+dx[i],ny=f.y+dy[i];
            if(nx<0||ny<0||nx>1000||ny>1000||mud[nx][ny])continue;//这里原来是<-500或>500就不能走，而现在变成<(-500+500=)0或者>(500+500=)1000
            mud[nx][ny]=true;//标记访问
            q[++rear]=(node){nx,ny,f.step+1};//入队
            if(nx==ex+500&&ny==ey+500)//注意结束坐标也要加500
            {
                printf("%d",q[rear].step);
                return 0;//注意BFS找的是最优解，所以可以在输出后直接结束程序
            }
        }
    }
    return 0;
}

当然，要考虑数组下标为负的时候，我们很难忘记$\color{red}\text{STL(标准模板库)}$中的一个秘宝（标准模板库里面全是好东西），即$\text{map}$。

$\text{map}$可以实现两个任意类型变量的一一对应。来看几个例子：

#include<map>//需要引入头文件
map<int,int>m1;//实现int和int之间一一对应的关系
map<string,bool>m2;//实现string和int之间一一对应的关系
m1[-1]=5;//这里可以把-1位置赋值为5
m2["AC is fun"]=true;

然而，这里需要二维数组，表面上看起来没有办法实现。但由于递归是合法的，所以我们可以将两个$\text{map}$进行叠加，即：

map<int,map<int,bool>>mud;//最终的结果是bool类型，相当于bool mud[][];，只不过下标范围不同（int可以为负）

这样，我们就可以更加方便地实现本题的负数坐标问题了（尽管常数不小）：

//注意定义了map之后，前面的500都不需要加了
#include<bits/stdc++.h>//map头文件在万能头文件中
using namespace std;
int ex,ey,n,front=1,rear=1,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
map<int,map<int,bool>>mud;
struct node
{
    int x,y,step;
}q[1000001];
int main()
{
    scanf("%d%d%d",&ex,&ey,&n);
    for(int i=0,a,b;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        mud[a][b]=true;
    }
    while(front<=rear)
    {
        node f=q[front++];
        for(int i=0;i<4;i++)
        {
            int nx=f.x+dx[i],ny=f.y+dy[i];
            if(nx<-500||ny<-500||nx>500||ny>500||mud[nx][ny])continue;
            mud[nx][ny]=true;
            q[++rear]=(node){nx,ny,f.step+1};
            if(nx==ex&&ny==ey)
            {
                printf("%d",q[rear].step);
                return 0;
            }
        }
    }
    return 0;
}

然而，$\text{STL}$常数太大，解决方法有：

• 开启$\text{O2}$

• 语言使用$\text{C++17}$

• 和$\text{unordered\_map}$互换

注：$\text{map}$和$\text{unordered\_map}$的时间复杂度极不稳定，可以直接互换（不用万能头文件的话要换头文件）。但是在竞赛中建议不要冒这么大的风险，最好还是少用$\text{STL}$为妙。

对于本题来说，最好的方法还是把横纵坐标全部加上$500$，并把二维数组开到$1000$以上，因为这样下来，$10$个测试点的运行时间可以控制在$\text{100ms}$以内。因此，任何东西都有利有弊——$\text{map}$虽说方便好用，但时间常数是很大的。根据实际情况合理应用才是最关键的。