这道题虽然有个坑,虽然有意识地避开,但是在那些测试点还是过不去,就是在遇到“+”时(已经走过的地方)有更优的路线就重新push进队列,我这样的做法有什么问题吗?
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
int x,y,l,r;
};
int n,m,sx,sy,l,r,ans=1;
node off[4]={{0,1,0,1},{1,0,0,0},{0,-1,1,0},{-1,0,0,0}};
char a[2005][2005];
node p[2005][2005];
int main(){
cin>>n>>m>>sx>>sy>>l>>r;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
queue<node>q;
q.push((node){sx,sy,0,0});
a[sx][sy]='+';
p[1][1].l=p[1][1].r=0;
while(!q.empty()){
node k=q.front();
for(int i=0;i<4;i++){
int x=k.x+off[i].x;
int y=k.y+off[i].y;
int nl=k.l+off[i].l;
int nr=k.r+off[i].r;
if(x>=1&&x<=n&&y>=1&&y<=m){
if(a[x][y]=='.'&&nl<=l&&nr<=r){
q.push((node){x,y,nl,nr});
p[x][y].l=nl;
p[x][y].r=nr;
a[x][y]='+';
ans++;
}
else if(a[x][y]=='+'){
if(nl<p[x][y].l&&nr<p[x][y].r){
q.push((node){x,y,nl,nr});
p[x][y].l=nl;
p[x][y].r=nr;
}
else a[x][y]='*';
}
}
}
q.pop();
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<a[i][j];
// }
// cout<<endl;
// }
cout<<ans;
return 0;
}