@[From_our_star](/user/494421) 是这题吗,不对啊
by __f0r_1_1n_ran9e__ @ 2023-02-18 11:38:42
@[__for_i_in_range__](/user/747879) 是这题,但是这是我旁边的人写的
by Exoplanet @ 2023-02-18 11:40:07
@[From_our_star](/user/494421) 6,传送门呢
by __f0r_1_1n_ran9e__ @ 2023-02-18 11:41:13
稍微看了一下,有一行代码错了
by shebshijun @ 2023-02-18 11:41:42
成功AC代码:
```c
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;//迷宫大小
int c1,d1;//终点地点
char a[301][301];//迷宫地图
int vis[301][301];//已走路径
int x;
int y;//当前位置
int e[4]={0,0,1,-1};
int r[4]={1,-1,0,0};//方向数组
struct s
{
int qd,zd,bs;//qd:x zd:y bs:步数
}ans[100000];//队列数组
int fy(int q,int w)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[q][w]==a[i][j]&&(q!=i||w!=j))//寻找到传送门另一头
{
x=i;
y=j;
return 0;//传送
}
}
}
}
int bfs()
{
int head=0,tail=1;
do{
head++;
if(a[ans[head].qd][ans[head].zd]>='A'&&a[ans[head].qd][ans[head].zd]<='Z')
{
fy(ans[head].qd,ans[head].zd);//寻找传送门
ans[head].qd=x;
ans[head].zd=y;
}//传送完成
for(int i=0;i<4;i++)
{
int hzb=ans[head].qd+e[i];
int zzb=ans[head].zd+r[i];//下一步可选位置
if(vis[hzb][zzb]==0&&a[hzb][zzb]!='#')//是否可走
{
vis[hzb][zzb]=1;
tail++;
ans[tail].qd=hzb;
ans[tail].zd=zzb;
ans[tail].bs=ans[head].bs+1;//ans[tail].bs++;
if(ans[tail].qd==c1&&ans[tail].zd==d1)//寻找到终点
{
printf("%d\n",ans[tail].bs);
return 0;
}
}
}
}while(head<=tail);//模拟队列
}
int main()
{
int q,d;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&a[i][j]);
if(a[i][j]=='@')
{
q=i;d=j;//起点设置
}
if(a[i][j]=='=')
{
c1=i;d1=j;//终点设置
}
}
}
//printf("3");
vis[q][d]=1;
ans[1].qd=q;
ans[1].zd=d;
bfs();
return 0;
}
```
成功AC记录:[R102377347 记录详情](https://www.luogu.com.cn/record/102377347)
by shebshijun @ 2023-02-18 11:42:49
现在82分
```
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int c1,d1;
char a[301][301];
int vis[301][301];
int x;
int y;
int e[4]={0,0,1,-1};
int r[4]={1,-1,0,0};
struct s{
int qd,zd,bs;
}ans;
queue<s>que;
int fy(int &q,int &w)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[q][w]==a[i][j]&&(q!=i||w!=j))
{
q=i;
w=j;
return 0;
}
}
}
}
int bfs()
{
while(que.size()){
s ver=que.front();
que.pop();
if(ver.qd==c1&&ver.zd==d1)
{
printf("%d\n",ver.bs);
return 0;
}
if(a[ver.qd][ver.zd]>='A'&&a[ver.qd][ver.zd]<='Z')
{
fy(ver.qd,ver.zd);
}
for(int i=0;i<4;i++)
{
int hzb=ver.qd+e[i];
int zzb=ver.zd+r[i];
if(vis[hzb][zzb]==0&&a[hzb][zzb]!='#'&&hzb>=0&&zzb>=0&&hzb<n&&hzb<m)
{
vis[hzb][zzb]=1;
ans.qd=hzb;
ans.zd=zzb;
ans.bs=ver.bs+1;
que.push(ans);
}
}
}
}
int main()
{
int q,d;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&a[i][j]);
if(a[i][j]=='@')
{
q=i;d=j;
}
if(a[i][j]=='=')
{
c1=i;d1=j;
}
}
}
//printf("3");
vis[q][d]=1;
ans.qd=q;
ans.zd=d;
ans.bs=0;
que.push(ans);
bfs();
return 0;
}
```
by Exoplanet @ 2023-02-18 11:43:05
@[From_our_star](/user/494421) 稍微写了下注释,可能不太好看,代码第53行
```cpp
ans[tail].bs++
```
意思应为“当前已经花费步数加一”,该位置原本没走过所以 bs 为0,应该改为前一个位置的 bs 加一,该行改为以下代码
```cpp
ans[tail].bs=ans[head].bs+1;
```
改完后结果正确
by shebshijun @ 2023-02-18 11:46:17
@[From_our_star](/user/494421) 是tle吗,那就是传送门寻找超时了,先预处理每个传送门坐标,不要每次查找传送地点
by __f0r_1_1n_ran9e__ @ 2023-02-18 11:46:27
@[__for_i_in_range__](/user/747879) 是WA
by Exoplanet @ 2023-02-18 11:48:10
@[__for_i_in_range__](/user/747879) 应该是WA,步数计算错了(这位应该是匿名提交,查不到提交记录)
by shebshijun @ 2023-02-18 11:49:01