Labyrinth

一看就是bfs题，但是单纯的想，就错了 错误代码：

#include<iostream> #include<cstring> #include<queue> using namespace std; const int N=2010; char g[N][N]; unsigned int yll[N][N]; unsigned int ylr[N][N]; bool vis[N][N]; int n,m; int sx,sy; int l,r; struct node{ int x; int y; int lst; int rst; }; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; void bfs() { queue<node>q; q.push({sx-1,sy-1,0,0}); vis[sx-1][sy-1]=true; yll[sx-1][sy-1]=l; ylr[sx-1][sy-1]=r; while(q.size()) { auto t=q.front(); q.pop(); int x=t.x; int y=t.y; int ll=t.lst; int rr=t.rst; //cout<<x<<' '<<y<<' '<<ll<<' '<<rr<<endl; for(int i=0;i<4;i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx<0||ty<0||tx>=n||ty>=m||g[tx][ty]=='*') continue; if(vis[tx][ty] && yll[tx][ty]>(l - ll - (dy[i]<0)) && ylr[tx][ty]>(r-rr-(dy[i]>0))) continue; if(dy[i]>0 && rr+1>r) continue; if(dy[i]<0 && ll+1>l) continue; vis[tx][ty]=true; yll[tx][ty]=max((int)yll[tx][ty],l-ll-(dy[i]<0)); ylr[tx][ty]=max((int)ylr[tx][ty],r-rr-(dy[i]>0)); q.push({tx,ty,ll+(dy[i]<0),rr+(dy[i]>0)}); } } } int main() { cin >> n >>m; cin >> sx >> sy; cin >> l >> r; for(int i=0;i<n;i++) cin>>g[i]; int res=0; bfs(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) res+=vis[i][j]; cout<<res<<endl; return 0; }

原因是bfs过程中能走的不一定是最优的，也就是先到的点不一定是最优的，由于vis数组的原因，他会把后到的优秀的点给排掉，那么我们需要一个最优数组，分别记录走到该点能（左右）继续走最多的路数 代码：

#include<iostream> #include<cstring> #include<queue> using namespace std; const int N=2020; char g[N][N]; struct nn{ int ll; int rr; }; nn yl[N][N]; bool vis[N][N]; int n,m; int sx,sy; int l,r; struct node{ int x; int y; int lst; int rst; }; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; void bfs() { queue<node>q; q.push({sx-1,sy-1,0,0}); vis[sx-1][sy-1]=true; yl[sx-1][sy-1].ll=l; yl[sx-1][sy-1].rr=r; while(q.size()) { auto t=q.front(); q.pop(); int x=t.x; int y=t.y; //cout<<x<<' '<<y<<endl; int ll=t.lst; int rr=t.rst; //cout<<x<<' '<<y<<' '<<ll<<' '<<rr<<endl; for(int i=0;i<4;i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx<0||ty<0||tx>=n||ty>=m||g[tx][ty]=='*') continue; if(vis[tx][ty] && yl[tx][ty].ll>=(l-ll-(dy[i]<0)) && yl[tx][ty].rr>=(r-rr-(dy[i]>0))) continue; if(dy[i]>0 && rr+1>r) continue; if(dy[i]<0 && ll+1>l) continue; vis[tx][ty]=true; yl[tx][ty].ll=max(yl[tx][ty].ll,l-ll-(dy[i]<0)); yl[tx][ty].rr=max(yl[tx][ty].rr,r-rr-(dy[i]>0)); q.push({tx,ty,ll+(dy[i]<0),rr+(dy[i]>0)}); } } } int main() { cin >> n >>m; cin >> sx >> sy; cin >> l >> r; for(int i=0;i<n;i++) cin>>g[i]; int res=0; bfs(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) res+=vis[i][j]; cout<<res<<endl; return 0; }