VJ SWPU-ACM省赛集训赛ONE J Right turn

【类型】

模拟

【Tip】

我的代码感觉上很对…然而莫名其妙总WA.然后把代码改成网上搜的题解的思路,A了…

我一开始的思路是floyd判圈法,若会碰到同一个路障第二次,则一定无法逃出去.

这个思路是错的,因为有可能在同一个点转的方向不同,所以如果经过同一个点两次有可能逃出去.

但每个点最多只能经过三次,第四次时一定是一个圈.所以判断是否经过一个点四次就好了.依然是floyd判圈法.不过要判四次.

然后成型代码如下.

【WA Code1】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf("%lld",&(N))
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<"="<<(x)<<endl;
#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,bool> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(1){
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>X){
                    if(mp[make_pair(Just[i],Y)]) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]=true;
                    flag=1;
                    X=Just[i]-1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<Y){
                    if(mp[make_pair(X,Just[i])]) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]=true;
                    Y=Just[i]+1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<X){
                    if(mp[make_pair(Just[i],Y)]) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]=true;
                    flag=1;
                    X=Just[i]+1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    if(mp[make_pair(X,Just[i])]) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]=true;
                    Y=Just[i]-1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }
    }
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf("%d%d",&node.first,&node.second);
            mp[node]=false;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        map<int,vector<int> >::iterator it;
        for(it=EdgeX.begin();it!=EdgeX.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        for(it=EdgeY.begin();it!=EdgeY.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        if(floyd()){
            printf("%d\n",step);
        }else{
            printf("-1\n");
        }
    }
    return 0;
}

【简单修改后AC代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,int> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(1){
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>X){
                    if(mp[make_pair(Just[i],Y)]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]++;
                    flag=1;
                    X=Just[i]-1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<Y){
                    if(mp[make_pair(X,Just[i])]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]++;
                    Y=Just[i]+1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<X){
                    if(mp[make_pair(Just[i],Y)]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]++;
                    flag=1;
                    X=Just[i]+1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    if(mp[make_pair(X,Just[i])]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]++;
                    Y=Just[i]-1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }
    }
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf(“%d%d”,&node.first,&node.second);
            mp[node]=0;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        map<int,vector<int> >::iterator it;
        for(it=EdgeX.begin();it!=EdgeX.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        for(it=EdgeY.begin();it!=EdgeY.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        if(floyd()){
            printf(“%d\n”,step);
        }else{
            printf(“-1\n”);
        }
    }
    return 0;
}

【跟着题解AC Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,bool> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(step<=4*N+1){
        int tmpx=-INF,tmpy=-INF;
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size();
            rep(i,si){
                if(Just[i]>X){
                    tmpy=Y;
                    if(tmpx!=-INF) tmpx=min(tmpx,Just[i]);
                    else tmpx=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
    //            if(mp[make_pair(tmpx,Y)]) return false;
     //           mp[make_pair(tmpx,Y)]=true;
                X=tmpx-1;
                step++;
                t=(t+1)%4;
            }

        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]<Y){
                    tmpx=X;
                    flag=1;
                    if(tmpy!=-INF) tmpy=max(tmpy,Just[i]);
                    else tmpy=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
  //              if(mp[make_pair(X,tmpy)]) return false;
 //               mp[make_pair(X,tmpy)]=true;
                Y=tmpy+1;
                step++;
                t=(t+1)%4;
            }
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]<X){
                    flag=1;
                    tmpy=Y;
                    if(tmpx!=-INF) tmpx=max(tmpx,Just[i]);
                    else tmpx=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
 //               if(mp[make_pair(tmpx,Y)]) return false;
 //               mp[make_pair(tmpx,Y)]=true;
                X=tmpx+1;
                step++;
                t=(t+1)%4;
            }
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    tmpx=X;
                    flag=1;
                    if(tmpy!=-INF) tmpy=min(tmpy,Just[i]);
                    else tmpy=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
 //              if(mp[make_pair(X,tmpy)]) return false;
  //              mp[make_pair(X,tmpy)]=true;
                Y=tmpy-1;
                step++;
                t=(t+1)%4;
            }
        }
    }
    return false;
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf(“%d%d”,&node.first,&node.second);
//            mp[node]=false;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        if(floyd()){
            printf(“%d\n”,step);
        }else{
            printf(“-1\n”);
        }
    }
    return 0;
}

UVa 11549

【题解】

Floyd判圈法

【Code】

#include<bits/stdc++.h>
using namespace std;

int buf[200];
int next(int n,int k){
    if(!k) return 0;
    int p=0,i=0;
    long long RES=(long long)k*k;
    while(RES>0){buf[i++]=RES%10;RES/=10;}
    if(n>i)n=i;
    for(int t=0;t<n;++t)p=p*10+buf[–i];
    return p;
}

void floyd_check(int n,int k){
        int k1=k,k2=k,ans=k;//ans=k
        do{
            k1=next(n,k1);
            k2=next(n,k2);if(k2>ans)ans=k2;
            k2=next(n,k2);if(k2>ans)ans=k2;

        }while(k1!=k2);
        printf(“%d\n”,ans);
}

int main(){
    int T,n,go;
    scanf(“%d”,&T);
    while(T–){
        scanf(“%d%d”,&n,&go);
        floyd_check(n,go);
    }
    return 0;
}