|
### TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431)
DFS
E - 网格反射
问题陈述
有一个带有行和列的网格。我们将顶部的第 - 行和左侧的第 - 列的单元格称为 单元格 。每个单元格上最多放置一面镜子。HWij(i,j)
高桥站在牢房的左侧，青木站在牢房的右侧。高桥拿着手电筒，从牢房的左侧向右照射光线。在这里，假设手电筒的光不会漫射，并且是直线传播的光线。(1,1)(H,W)(1,1)
高桥的目标是利用网格中的镜子将手电筒的光线传递给青木。
镜子放置分为三种类型。当光线照射到镜子上时，光线的方向会根据镜子的位置而变化。对于每个镜子放置，每个入口方向的退出方向如下图所示。
网格上的镜子位置由长度为 ： 的字符串表示。当 的第 - 个字符是 时，cell 是 A 型;当它是时，细胞是B型;当它是时，单元格是 C 型。HWS1,S2,…,SHjSiA(i,j)B(i,j)C(i,j)
高桥可以执行以下作任意次数，将光线传递给青木：
- 选择一个单元格并将该单元格的镜像位置更改为其他类型。
找到向青木输送光线所需的最少作次数。
你会得到测试用例;找到每个的答案。T
```cpp
#include
#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
priority_queue 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 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 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 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 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
#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
priority_queue 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 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 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 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 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;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
