萌新刚学OI 0.01ms,bfs写挂求助QwQ
  • 板块CF1063B Labyrinth
  • 楼主LYqwq
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/8/3 14:54
  • 上次更新2023/10/27 17:13:50
查看原帖
萌新刚学OI 0.01ms,bfs写挂求助QwQ
399116
LYqwq楼主2022/8/3 14:54
#include <iostream>
using namespace std;
const int N=2e3+5;
struct node{
    int x,y,l,r;
}q[N*N];
int n,m,sx,sy,ml,mr;
int l,r,ans=1;
char mp[N][N];
int lct[N][N],rct[N][N];
node dt[4]={{-1,0,0,0},{1,0,0,0},{0,-1,1,0},{0,1,0,1}};

void bfs(){
    l=1;
    q[++r]={sx,sy,0,0};
    mp[sx][sy]='$';
    lct[sx][sy]=rct[sx][sy]=0;
    while(l<=r){
        node p=q[l++];
        for(int i=0; i<4; i++){
            int x=p.x+dt[i].x,y=p.y+dt[i].y;
            int l=p.l+dt[i].l,r=p.r+dt[i].r;
            if(x>=1 && x<=n && y>=1 && y<=m)
                if(mp[x][y]=='.' && l<=ml && r<=mr){
                    q[++r]={x,y,l,r};
                    lct[x][y]=l,rct[x][y]=r;
                    mp[x][y]='$';
                    ans++;
                }else if(mp[x][y]=='$' && l<lct[x][y] && r<rct[x][y]){
                    q[++r]={x,y,l,r};
                    lct[x][y]=l,rct[x][y]=r;
                }
        }
    }
}

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ml,&mr);
    for(int i=1; i<=n; i++)
        scanf("%s",mp[i]+1);
    bfs();
    printf("%d\n",ans);
    for(int i=1; i<=n; i++)
        printf("%s\n",mp[i]+1);
    return 0;
}

样例不过/kk

2022/8/3 14:54
加载中...