点击这里查看原题
其实思路不难，对于每个点分三种情况。
没走过这个点，但却有颜色，无解走过这个点，有颜色，那么最早时刻在最后一次经过该点之后走过这个点，没有颜色，那么最晚时刻在最后一次经过该点之前于是，将所有点加入set，倒序模拟一遍，依次删除所有走过的点，同时更新答案即可
/* User:Small Language:C++ Problem No.:4879 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int M=1e6+5; int h,w,n,op[M],d[M],nex[4][2]={-1,0,0,1,1,0,0,-1},curx,cury; ll t,L,R; set<int> sx[M],sy[M]; char s[M]; int getop(char *s){ if(s[0]=='u') return 0; if(s[0]=='r') return 1; if(s[0]=='d') return 2; if(s[0]=='l') return 3; } char ask(int x,int y,bool flag){ if(flag) swap(x,y); return s[x*w+y]; } void solve(set<int> &s,int st,int ed,ll tl,int wh,bool flag){ int l=st,r=ed; if(l>r) swap(l,r); for(set<int>::iterator it=s.lower_bound(l);it!=s.end()&&*it<=r;){ if(flag) sx[*it].erase(sx[*it].find(wh)); else sy[*it].erase(sy[*it].find(wh)); if(ask(wh,*it,flag)=='#') L=max(L,tl-abs(*it-st)); else R=min(R,tl-abs(*it-st)-1); s.erase(it++); } } int main(){ freopen("data.in","r",stdin);// scanf("%d%d%d",&h,&w,&n); for(int i=0;i<h;i++) scanf("%s",s+i*w); for(int i=1;i<=n;i++){ char tmp[10]; scanf("%s%d",tmp,&d[i]); op[i]=getop(tmp); } for(int i=0;i<h;i++) for(int j=0;j<w;j++) sx[i].insert(j); for(int i=0;i<w;i++) for(int j=0;j<h;j++) sy[i].insert(j); curx=h-1; cury=0; t=1; for(int i=1;i<=n;i++){ t+=d[i]; curx+=nex[op[i]][0]*d[i]; cury+=nex[op[i]][1]*d[i]; } R=t; for(int i=n;i;i--){ int tp=(op[i]+2)%4; int nx=curx+nex[tp][0]*d[i],ny=cury+nex[tp][1]*d[i]; if(tp%2) solve(sx[curx],cury,ny,t,curx,0); else solve(sy[cury],curx,nx,t,cury,1); t-=d[i]; curx=nx; cury=ny; } for(int i=0;i<h&&L<=R;i++){ for(set<int>::iterator it=sx[i].begin();it!=sx[i].end();it++){ if(ask(i,*it,0)=='#'){ L=R+1; break; } } } if(L>R) L=R=-1; printf("%lld %lld\n",L,R); return 0; }