题目链接：https://www.acwing.com/problem/content/2021/

题解

将每个小方格看作一个点，从当前点到达相邻的方格时，若该方格有障碍物则看作边权为1，没有则看为0，该问题就可转换为从某个点到(0,0)点的最短路。

代码

#include 
#include 
#include 
#include 
#define x first
#define y second

using namespace std;

typedef pair PII;
const int N = 1010;
int n,sx,sy;
int a,b;
bool v[N][N],k[N][N];
int dist[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(int x,int y) {
    deque q;
    q.push_front({x,y});
    memset(dist,0x3f,sizeof dist);
    dist[x][y] = 0;
    
    while(q.size()) {
        auto t = q.front();
        q.pop_front();
        
        if(k[t.x][t.y]) continue;
        k[t.x][t.y] = 1;
        
        if(t.x == 0 && t.y == 0) break;
        
        for (int i = 0 ; i < 4 ; i ++ ) {
            int xx = t.x + dx[i] , yy = t.y + dy[i];
            if(xx >= 0 && xx < N && yy >= 0 && yy < N) {
                int u = v[xx][yy];
                if(dist[xx][yy] > dist[t.x][t.y] + u) {
                    dist[xx][yy] = dist[t.x][t.y] + u;
                    if(!u) q.push_front({xx,yy});
                    else q.push_back({xx,yy});
                }
            }
        }
    }
    return dist[0][0];
}

int main()
{
    cin >> n >> sx >> sy;
    for (int i = 0 ; i < n ; i ++ ) {
        cin >> a >> b;
        v[a][b] = 1;
    }
    
    int ans = bfs(sx,sy);
    
    cout << ans << endl;
    
    return 0;
}