本文共 1726 字，大约阅读时间需要 5 分钟。

【题目】

【题解】

模拟或者记忆化搜索都可以，时间复杂度O(NM)。

【模拟】

#include
   
    using namespace std;int dx[]={-1,1,0,0}; //上，下，左，右int dy[]={0,0,-1,1};int main(){    int n,m; char mp[505][505];    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);    int x,y,ans,t;    for(int i=1;i<=m;i++)    {        x=1,y=i,ans=-1,t=1;        while(x>0&&x<=n&&y>0&&y<=m)        {            if(mp[x][y]=='\\') t=(t+2)%4;            else if(mp[x][y]=='/') t=3-t;            x+=dx[t],y+=dy[t];            //printf("x=%d,y=%d\n",x,y);            if(x==n+1) ans=y;        }        printf("%d\n",ans);    }    return 0;}
   

【记忆化搜索】

#include
   
    using namespace std;int n,m;char mp[505][505];int dfs(int x,int y,int dx,int dy){    if(x==n+1) return y;    if(x==0||y==0||y==m+1) return -1;    if(mp[x][y]=='.') return dfs(x+dx,y+dy,dx,dy);    if(mp[x][y]=='/') return dfs(x-dy,y-dx,-dy,-dx);    return dfs(x+dy,y+dx,dy,dx);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);    for(int i=1;i<=m;i++) printf("%d\n",dfs(1,i,1,0));    return 0;}
   

【题目】

【题解】

贪心，每次走2^p肯定比每次走1快，然后就用2^p走法与传送法阵走法进行比较，从u到v是用2^p走法还是传送法阵走法比较快。

【贪心】

#include 
   
    using namespace std;typedef long long ll;ll a[35];void init(){    a[0]=1;    for(int i=1;i<=30;i++) a[i]=a[i-1]*2;}ll cul(ll u,ll v) //2^p走法{    ll sum=0;    while(u
    
     =0;i--)            if(u+a[i]<=v)            {                u+=a[i]; sum++;                break;            }    return sum;}int main(){    init();    ll n; int k; scanf("%lld%d",&n,&k);    ll ans; ans=cul(1,n);    while(k--)    {        int u,v; scanf("%d%d",&u,&v);        if(u==v) continue;        if(u>v) swap(u,v);        ans=min(ans,cul(1,u)+cul(v,n)+1);    }    printf("%lld\n",ans);    return 0;}
    
   

转载地址：http://lfben.baihongyu.com/