01BFS模板WA40

这题难道不是贪心吗QaQ（）

贪心+BFSQaQ（猜测：贪心可以减复杂度）

但是看起来可以用BFS直接解

@2345安全卫士 对呀我是贪心，这道题目是一道01BFS模板

o，ok

是这个吗，这个不是普通把魔法给进去吗QaQ

@2345安全卫士 是的呀这道题目是模板，但是我用的不是普通队列是双向队列

我吃柠檬去，啊不是我吃饭去了，下课了

按照老师说的改了还是WA40：

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
I AK IOI;
int n,m,Cx,Cy,Dx,Dy,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char mapa[1005][1005];
struct node{
	int x,y,step;
};
int bfs(){
	deque<node>q;
	q.push_back({Cx,Cy,0});
	bool vis[1005][1005];
	memset(vis,0,sizeof vis);
	vis[Cx][Cy]=1;
	while(!q.empty()){
		node t=q.front();
		q.pop_front();
		if(t.x==Dx&&t.y==Dy)return t.step;
		for(int i=0;i<4;i++){
			int nx=t.x+dx[i],ny=t.y+dy[i];
			if(nx>0&&nx<=n&&ny>0&&ny<=m&&vis[nx][ny]==0&&mapa[nx][ny]=='.'){
				vis[nx][ny]=1;
				q.push_front({nx,ny,t.step});
			}
		}
		for(int i=t.x-2;i<=t.x+2;i++){
			for(int j=t.y-2;j<=t.y+2;j++){
				if(i>0&&i<=n&&j>0&&j<=m&&vis[i][j]==0&&mapa[i][j]=='.'){
					vis[i][j]=1;
					q.push_back({i,j,t.step+1});
				}
			}
		}
	}
	return -1;
}
signed main(){
	cin>>n>>m>>Cx>>Cy>>Dx>>Dy;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mapa[i][j];
	cout<<bfs();
	i_ak ioi;
}

我用的不是双端队列
我是先把不用魔法走的情况入队，再把用魔法走的情况入队，同时如果用魔法能实现相同的上下左右移动，则跳过
虽然我也WA40

e。我静静（难兄难弟呀，就我们两个没有做出来 @黄飞栋

感觉deque加入 step 后，这里 vis[nx][ny]==-1 要改成 t.step < vis[nx][ny] (vis初始化为INF)
后面要改成 t.step+1 < vis[i][j]

@鲁纶 为什么我这样会导致哪里出错？

后来者会不会有魔法用的少些的？

@鲁纶 e啥意思？有点没听懂

老师好像在QQ群里给标准答案了

@黄飞栋 但是我也没看出我哪里录错了呀？（老师也没看出来

我觉得你可以先把define什么的删掉，换成常规代码，再一行一行地对着看一遍

扔给 deepseek

@孙正雨 不要能帮我求调吗？

我AC惹:)
就是我的那个思路，你照着那个思路做做
重写一遍也行

$$不是我写的，是别人写的$$