社区讨论

萌新刚学OI 0.01ms,bfs写挂求助QwQ

CF1063BLabyrinth参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo8ec36r
此快照首次捕获于
2023/10/27 17:13
2 年前
此快照最后确认于
2023/10/27 17:13
2 年前
查看原帖
CPP
#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

回复

7 条回复,欢迎继续交流。

正在加载回复...