AcWing 2019. 拖拉机
原题链接
中等
作者:
修仙修仙
,
2024-10-01 19:44:43
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int t;
int m,n;
const int N=1010;
bool st[N][N],vis[N][N];
int x,y;
char s[N][N];
int dist[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void bfs()
{
memset(dist,0x3f,sizeof dist);
deque<pair<int,int>>q;
q.push_back({x,y});
dist[x][y]=0;
while(q.size())
{
auto [x,y]=q.front();
q.pop_front();
if(st[x][y])continue;
st[x][y]=1;
for(int i=0;i<4;i++)
{
int x1=x+dx[i];
int y1=y+dy[i];
if(x1<0||x1>=N||y1<0||y1>=N)continue;
int w=vis[x1][y1];
if(dist[x1][y1]>dist[x][y]+w)
{
dist[x1][y1]=dist[x][y]+w;
if(w)q.push_back({x1,y1});
else q.push_front({x1,y1});
}
}
}
}
int main()
{
int t;
cin>>t>>x>>y;
x++;
y++;
for(int i=1;i<=t;i++)
{
int x,y;
cin>>x>>y;
x++,y++;
vis[x][y]=1;
}
bfs();
cout<<dist[1][1]<<"\n";
}