当前位置： 首页 > news >正文

Atcoder-ABC-431-E

news 2026/6/11 9:27:34

### TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431)
DFS

E - 网格反射

 

问题陈述

 

有一个带有行和列的网格。我们将顶部的第 - 行和左侧的第 - 列的单元格称为 单元格 。每个单元格上最多放置一面镜子。HWij(i,j)

 

高桥站在牢房的左侧，青木站在牢房的右侧。高桥拿着手电筒，从牢房的左侧向右照射光线。在这里，假设手电筒的光不会漫射，并且是直线传播的光线。(1,1)(H,W)(1,1)

 

高桥的目标是利用网格中的镜子将手电筒的光线传递给青木。

 

镜子放置分为三种类型。当光线照射到镜子上时，光线的方向会根据镜子的位置而变化。对于每个镜子放置，每个入口方向的退出方向如下图所示。

 

  • A型（不放置镜子）

 

 

  • B型（连接左上和右下的对角线上放置一面镜子）

 

 

  • C型（镜子放置在连接右上和左下的对角线上）

 

 

网格上的镜子位置由长度为 ： 的字符串表示。当 的第 - 个字符是 时，cell 是 A 型;当它是时，细胞是B型;当它是时，单元格是 C 型。HWS1​,S2​,…,SH​jSi​A(i,j)B(i,j)C(i,j)

 

高桥可以执行以下作任意次数，将光线传递给青木：

 

  • 选择一个单元格并将该单元格的镜像位置更改为其他类型。

 

找到向青木输送光线所需的最少作次数。

 

你会得到测试用例;找到每个的答案。T


```cpp

#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define int long long
#define INF 2147483647
#define mod 998244353
#define N 610005
#define NO printf("No\n")
#define YES printf("Yes\n")

using namespace std;
int n,m,k,jk,ans,sum,num,cnt,tot;
int dis[N],vis[N][5],f[N];
char a[N];

void read(int &x){
    x=0;int ff=1;char ty;
    ty=getchar();
    while(!(ty>='0'&&ty<='9')){
        if(ty=='-') ff=-1;
        ty=getchar();
    }
    while(ty>='0'&&ty<='9')
        x=(x<<3)+(x<<1)+ty-'0',ty=getchar();
    x*=ff;return;
}

void write(int x){
    if(x==0){
        putchar('0');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    char asd[201];int ip=0;
    while(x) asd[++ip]=x%10+'0',x/=10;
    for(int i=ip;i>=1;i--) putchar(asd[i]);
    return;
}

struct Q{
    int sum,x,y,fx;
    bool operator<(const Q&A)const{
        return A.sum<sum;
    }
};

priority_queue<Q> q;
/*
1:->
2:^
3:v
4:<-
*/
int pd(int x,int fx){
    if(x==1){
        return fx;
    }else if(x==2){
        if(fx==1) return 3;
        if(fx==2) return 4;
        if(fx==3) return 1;
        if(fx==4) return 2;
    }else{
        if(fx==1) return 2;
        if(fx==2) return 1;
        if(fx==3) return 4;
        if(fx==4) return 3;
    }return 0;
}

pair<int,int> G(int x,int y,int fx){
    if(fx==1) return {x,y+1};
    if(fx==2) return {x-1,y};
    if(fx==3) return {x+1,y};
    if(fx==4) return {x,y-1};
    return {0,0};
}

void bfs(){
    while(!q.empty()) q.pop();
    q.push((Q){0,1,1,1});
    while(!q.empty()){
        Q A=q.top();q.pop();//wk(A.x),wk(A.y);wh(A.sum);
        if(A.x==n&&A.y==m+1&&A.fx==1) {ans=A.sum;return;}
        if(A.x<1||A.y<1||A.x>n||A.y>m||vis[A.x*m+A.y][A.fx]!=2e9) continue;
        vis[A.x*m+A.y][A.fx]=A.sum;
        if(a[A.x*m+A.y]=='A'){
            pair<int,int> to=G(A.x,A.y,pd(1,A.fx));
            if(vis[to.first*m+to.second][pd(1,A.fx)]==2e9) q.push((Q){A.sum,to.first,to.second,pd(1,A.fx)});
            to=G(A.x,A.y,pd(2,A.fx));
            if(vis[to.first*m+to.second][pd(2,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(2,A.fx)});
            to=G(A.x,A.y,pd(3,A.fx));
            if(vis[to.first*m+to.second][pd(3,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(3,A.fx)});
        }else if(a[A.x*m+A.y]=='B'){
            pair<int,int> to=G(A.x,A.y,pd(2,A.fx));
            if(vis[to.first*m+to.second][pd(2,A.fx)]==2e9) q.push((Q){A.sum,to.first,to.second,pd(2,A.fx)});
            to=G(A.x,A.y,pd(1,A.fx));
            if(vis[to.first*m+to.second][pd(1,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(1,A.fx)});
            to=G(A.x,A.y,pd(3,A.fx));
            if(vis[to.first*m+to.second][pd(3,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(3,A.fx)});
        }else{
            pair<int,int> to=G(A.x,A.y,pd(3,A.fx));
            if(vis[to.first*m+to.second][pd(3,A.fx)]==2e9) q.push((Q){A.sum,to.first,to.second,pd(3,A.fx)});
            to=G(A.x,A.y,pd(1,A.fx));
            if(vis[to.first*m+to.second][pd(1,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(1,A.fx)});
            to=G(A.x,A.y,pd(2,A.fx));
            if(vis[to.first*m+to.second][pd(2,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(2,A.fx)});
        }
    }
}

signed main()
{
    read(jk);while(jk--){
        read(n),read(m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                char ch=getchar();
                while(ch!='A'&&ch!='B'&&ch!='C') ch=getchar();
                a[i*m+j]=ch;
            }
        }
        for(int i=0;i<=n*m+m;i++) vis[i][1]=vis[i][2]=vis[i][3]=vis[i][4]=0;
        vis[n*m+m+1][1]=2e9;
        for(int i=m+1;i<=n*m+m;i++) vis[i][1]=vis[i][2]=vis[i][3]=vis[i][4]=2e9;
        ans=2e9;bfs();wh(ans);
    }
    return 0;
}

```

#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define int long long
#define INF 2147483647
#define mod 998244353
#define N 610005
#define NO printf("No\n")
#define YES printf("Yes\n")

using namespace std;
int n,m,k,jk,ans,sum,num,cnt,tot;
int dis[N],vis[N][5],f[N];
char a[N];

void read(int &x){
    x=0;int ff=1;char ty;
    ty=getchar();
    while(!(ty>='0'&&ty<='9')){
        if(ty=='-') ff=-1;
        ty=getchar();
    }
    while(ty>='0'&&ty<='9')
        x=(x<<3)+(x<<1)+ty-'0',ty=getchar();
    x*=ff;return;
}

void write(int x){
    if(x==0){
        putchar('0');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    char asd[201];int ip=0;
    while(x) asd[++ip]=x%10+'0',x/=10;
    for(int i=ip;i>=1;i--) putchar(asd[i]);
    return;
}

struct Q{
    int sum,x,y,fx;
    bool operator<(const Q&A)const{
        return A.sum<sum;
    }
};

priority_queue<Q> q;
/*
1:->
2:^
3:v
4:<-
*/
int pd(int x,int fx){
    if(x==1){
        return fx;
    }else if(x==2){
        if(fx==1) return 3;
        if(fx==2) return 4;
        if(fx==3) return 1;
        if(fx==4) return 2;
    }else{
        if(fx==1) return 2;
        if(fx==2) return 1;
        if(fx==3) return 4;
        if(fx==4) return 3;
    }return 0;
}

pair<int,int> G(int x,int y,int fx){
    if(fx==1) return {x,y+1};
    if(fx==2) return {x-1,y};
    if(fx==3) return {x+1,y};
    if(fx==4) return {x,y-1};
    return {0,0};
}

void bfs(){
    while(!q.empty()) q.pop();
    q.push((Q){0,1,1,1});
    while(!q.empty()){
        Q A=q.top();q.pop();//wk(A.x),wk(A.y);wh(A.sum);
        if(A.x==n&&A.y==m+1&&A.fx==1) {ans=A.sum;return;}
        if(A.x<1||A.y<1||A.x>n||A.y>m||vis[A.x*m+A.y][A.fx]!=2e9) continue;
        vis[A.x*m+A.y][A.fx]=A.sum;
        if(a[A.x*m+A.y]=='A'){
            pair<int,int> to=G(A.x,A.y,pd(1,A.fx));
            if(vis[to.first*m+to.second][pd(1,A.fx)]==2e9) q.push((Q){A.sum,to.first,to.second,pd(1,A.fx)});
            to=G(A.x,A.y,pd(2,A.fx));
            if(vis[to.first*m+to.second][pd(2,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(2,A.fx)});
            to=G(A.x,A.y,pd(3,A.fx));
            if(vis[to.first*m+to.second][pd(3,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(3,A.fx)});
        }else if(a[A.x*m+A.y]=='B'){
            pair<int,int> to=G(A.x,A.y,pd(2,A.fx));
            if(vis[to.first*m+to.second][pd(2,A.fx)]==2e9) q.push((Q){A.sum,to.first,to.second,pd(2,A.fx)});
            to=G(A.x,A.y,pd(1,A.fx));
            if(vis[to.first*m+to.second][pd(1,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(1,A.fx)});
            to=G(A.x,A.y,pd(3,A.fx));
            if(vis[to.first*m+to.second][pd(3,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(3,A.fx)});
        }else{
            pair<int,int> to=G(A.x,A.y,pd(3,A.fx));
            if(vis[to.first*m+to.second][pd(3,A.fx)]==2e9) q.push((Q){A.sum,to.first,to.second,pd(3,A.fx)});
            to=G(A.x,A.y,pd(1,A.fx));
            if(vis[to.first*m+to.second][pd(1,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(1,A.fx)});
            to=G(A.x,A.y,pd(2,A.fx));
            if(vis[to.first*m+to.second][pd(2,A.fx)]==2e9) q.push((Q){A.sum+1,to.first,to.second,pd(2,A.fx)});
        }
    }
}

signed main()
{
    read(jk);while(jk--){
        read(n),read(m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                char ch=getchar();
                while(ch!='A'&&ch!='B'&&ch!='C') ch=getchar();
                a[i*m+j]=ch;
            }
        }
        for(int i=0;i<=n*m+m;i++) vis[i][1]=vis[i][2]=vis[i][3]=vis[i][4]=0;
        vis[n*m+m+1][1]=2e9;
        for(int i=m+1;i<=n*m+m;i++) vis[i][1]=vis[i][2]=vis[i][3]=vis[i][4]=2e9;
        ans=2e9;bfs();wh(ans);
    }
    return 0;
}
http://www.zskr.cn/news/49428.html

相关文章：

  • 2025年石棉橡胶板厂家联系方式推荐：品质服务双保障
  • 两款开源工具推荐：科学信息检索导航 LaTeX 在线阅读器，科研效率提升利器！
  • 2025年比较好的工装定制TOP实力厂家推荐榜
  • 2025年11月天津电商财税公司榜单：五家服务商综合对比与选型建议
  • 2025年质量好的耙犁片TOP实力厂家推荐榜
  • 2025年比较好的面粉粮油厂家推荐及采购参考
  • 2025年热门的景区观光车用户好评厂家排行
  • 2025年质量好的卡扣式反弹器最新TOP厂家排名
  • 2025上海留学机构十大排名榜单大全
  • 2025上海口碑最好的留学机构是哪家公司的
  • 2025年质量好的昆明泡沫箱厂家推荐及选择参考
  • Unity+FGUI列表制作滚筒抽奖动画
  • 2025年靠谱的金属网厂家最新TOP实力排行
  • 完整教程：基于单片机的多模式自动洗衣机设计与实现
  • 2025年口碑好的工业型无线测力称重变送器厂家选购指南与推荐
  • 物理模型的图像去雾算法MATLAB实现
  • 2025年评价高的发热管缩管机行业内知名厂家排行榜
  • 2025年质量好的减速机配件厂家最新推荐权威榜
  • 2025年比较好的三菱印刷机胶辊厂家推荐及选择指南
  • 2025年比较好的精密减速器用户好评厂家排行
  • VonaJS: 序列化/数据脱敏(上)
  • 2025年比较好的10吨地磅TOP品牌厂家排行榜
  • 2025年靠谱的麦稻草浆挤浆机TOP实力厂家推荐榜
  • 2025新加坡金融科技节：看AI驱动的金融转型策略与“中国方案”
  • 2025年评价高的连续式台车炉厂家最新推荐权威榜
  • 软件测试— 测试分类 - 教程
  • 2025年知名的Lanny阀组比例阀厂家推荐及选购指南
  • 2025年知名的南京应急租发电机厂家最新推荐排行榜
  • 详细介绍：K8S（十四）—— K8s实战：HPA（Pod水平自动伸缩）完整部署与测试指南
  • 2025 年 11 月恒温恒湿系统厂家推荐排行榜，精加工车间恒温恒湿，厂房恒温恒湿，美术馆恒温恒湿，恒温恒湿仓库，计算机房恒温恒湿，档案室恒温恒湿系统，工业恒温恒湿，工厂车间恒温恒湿系统公司推荐