2 条题解

  • 0
    @ 2025-10-8 16:58:15
    #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
      @ 2025-10-8 16:58:05
      #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

      *【宽搜+set二分】冰上[USACO10FEB] Cows on Ice G(好题)

      信息

      ID
      1692
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      递交数
      7
      已通过
      6
      上传者