洛谷P1746 离开中山路

https://www.luogu.org/problemnew/show/P1746

思路：用广搜从起点开始，遍历所有可达的点，再往下遍历直到到达终点，所以能保证得到的结果一定是最优解

#include<bits/stdc++.h>

using namespace std;

int n,sx,sy,ex,ey;//sx、sy为起始坐标，ex、ey为目的地坐标

char a[][];

int dx[]={,,-,};

int dy[]={,,,-};//四个方向

struct node{//结构体

    int x,y,step;//step表示步数

};

queue <node> q;//建立一个队列

int bfs(int x,int y){//广搜函数

    node road;

    road.x=x,road.y=y,road.step=;//步数初始为0

    q.push(road);

    while(!q.empty()){

        road=q.front();

        q.pop();

        for(int i=;i<;i++){

            node now;//当前坐标和步数

            now.x=road.x+dx[i],now.y=road.y+dy[i];

            if(now.x>=&&now.x<=n&&now.y>=&&now.y<=n&&a[now.x][now.y]!=''){//判断是否越界并且不是店铺

                if(now.x==ex&&now.y==ey) return now.step;//找到目的地坐标就返回

                a[now.x][now.y]='';//标记防止重复走过

                now.step=road.step+;//步数+1

                q.push(now);//搜索下一层

            }

        }

    }

}

int main(){

    cin>>n;

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            cin>>a[i][j];

        }

    }

    cin>>sx>>sy>>ex>>ey;

    cout<<bfs(sx,sy);

    return ;

}