1 条题解
-
0
C++ :
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define x first #define y second const int N=1010; bool g[N][N],st[N][N]; int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; int dist[N][N]; int bfs(int x,int y) { memset(dist,0x3f,sizeof dist); dist[x][y]=0; deque<PII> q; q.push_back({x,y}); while(q.size()) { PII t=q.front(); q.pop_front(); if(st[t.x][t.y]) continue; st[t.x][t.y]=true; for(int i=0;i<4;i++) { int a=t.x+dx[i],b=t.y+dy[i]; int w=0; if(g[a][b]) w=1; if(a>=0&&a<N&&b>=0&&b<N) { if(dist[a][b]>dist[t.x][t.y]+w) { dist[a][b]=dist[t.x][t.y]+w; if(w==0) q.push_front({a,b}); else q.push_back({a,b}); } } } } return dist[0][0]; } int main() { int n,sx,sy; cin>>n>>sx>>sy; while(n--) { int x,y; cin>>x>>y; g[x][y]=1; } cout<<bfs(sx,sy); return 0; }
- 1
信息
- ID
- 782
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者