2 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define fi first #define se second typedef pair<int, int> node; int n; map < int , set < int > > rock_x; map < int , set < int > > rock_y; queue < node > q; map < node , int > dis; node b,g; set < int > :: iterator it;//表示是复制的来的 node go_up(node k){ set<int> y=rock_x[k.fi]; it=y.upper_bound (k.se) ; if (it==y.end()||(*it)-k.se<=1) return b; return node(k.fi,(*it)-1); }//往上查找 node go_down(node k){ set<int> y=rock_x[k.fi]; it=y.upper_bound (k.se) ; if (it==y.begin()||(k.se-(*(--it))<=1)) return b; return node(k.fi,(*it)+1); }//往下查找 node go_left(node k){ set<int> x=rock_y[k.se]; it=x.upper_bound (k.fi) ; if (it==x.begin()||(k.fi-(*(--it))<=1)) return b; return node((*it)+1,k.se); }//往左查找 node go_right(node k){ set<int> x=rock_y[k.se]; it=x.upper_bound (k.fi) ; if (it==x.end()||((*it)-k.fi<=1)) return b; return node((*it)-1,k.se); }//往右查找 int main(){ scanf("%d %d %d %d %d",&n,&b.fi,&b.se,&g.fi,&g.se); for (int i=1,x,y;i<=n;i++) scanf("%d %d",&x,&y),rock_x[x].insert(y),rock_y[y].insert(x);//建立每一个石头的行列的索引 q.push(b); dis[ b ]=0; while (!q.empty()){ node x=q.front(); q.pop(); node xx; xx=go_up(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; xx=go_down(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; xx=go_left(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; xx=go_right(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; if (dis[g]) break; }//bfs查找过程 printf("%d",dis[g]);//输出 return 0; } -
0
#include<bits/stdc++.h> using namespace std; #define fi first #define se second typedef pair<int , int > node; int n; map < int , set < int > > rock_x; map < int , set < int > > rock_y; queue < node > q; map < node , int > dis; node b,g; set < int > :: iterator it;//表示是复制的来的 node go_up(node k){ set<int> y=rock_x[k.fi]; it=y.upper_bound (k.se) ; if (it==y.end()||(*it)-k.se<=1) return b; return node(k.fi,(*it)-1); }//往上查找 node go_down(node k){ set<int> y=rock_x[k.fi]; it=y.upper_bound (k.se) ; if (it==y.begin()||(k.se-(*(--it))<=1)) return b; return node(k.fi,(*it)+1); }//往下查找 node go_left(node k){ set<int> x=rock_y[k.se]; it=x.upper_bound (k.fi) ; if (it==x.begin()||(k.fi-(*(--it))<=1)) return b; return node((*it)+1,k.se); }//往左查找 node go_right(node k){ set<int> x=rock_y[k.se]; it=x.upper_bound (k.fi) ; if (it==x.end()||((*it)-k.fi<=1)) return b; return node((*it)-1,k.se); }//往右查找 int main(){ scanf("%d %d %d %d %d",&n,&b.fi,&b.se,&g.fi,&g.se); for (int i=1,x,y;i<=n;i++) scanf("%d %d",&x,&y),rock_x[x].insert(y),rock_y[y].insert(x);//建立每一个石头的行列的索引 q.push(b); dis[ b ]=0; while (!q.empty()){ node x=q.front(); q.pop(); node xx; xx=go_up(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; xx=go_down(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; xx=go_left(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; xx=go_right(x); if (xx!=b&&!dis[xx]) q.push(xx),dis[xx]=dis[x]+1; if (dis[g]) break; }//bfs查找过程 printf("%d",dis[g]);//输出 return 0; }
- 1
信息
- ID
- 1692
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 7
- 已通过
- 6
- 上传者