01BFS模板WA40

问题讨论区 普及段
1

题目： 智灵班寒假普及±-搜索综合 - 信友队

代码：

#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;
};
int bfs(){
	deque<node>q;
	q.push_front({Cx,Cy});
	int vis[1005][1005];
	memset(vis,-1,sizeof vis);
	vis[Cx][Cy]=0;
	while(!q.empty()){
		node t=q.front();
		q.pop_front();
		if(t.x==Dx&&t.y==Dy)return vis[t.x][t.y];
		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]==-1&&mapa[nx][ny]=='.'){
				vis[nx][ny]=vis[t.x][t.y];
				q.push_front({nx,ny});
			}
		}
		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]==-1&&mapa[i][j]=='.'){
					vis[i][j]=vis[t.x][t.y]+1;
					q.push_back({i,j});
				}
			}
		}
	}
	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;
}
2

题目发过来
我没权限看

3

@杨思越

screenshotnoscalead3198b4-079f-447f-ac1a-d05850c9c6ca
screenshotnoscalead3198b4-079f-447f-ac1a-d05850c9c6ca964×1523 150 KB

4

这个可以考虑一下

5

@郭子路 嗯嗯，哪里错了？实在看不出来

6

题目看不清（可能我眼睛有问题），能分两段发吗

7

@2345安全卫士 好的等一下

8

@2345安全卫士 这是题目：

screenshotnoscaleb25a7321-288e-4d3b-9b49-0b68d29291ae
screenshotnoscaleb25a7321-288e-4d3b-9b49-0b68d29291ae1581×1508 228 KB

screenshotnoscalef52b7428-d239-46ee-8a5f-988fb639ad2e
screenshotnoscalef52b7428-d239-46ee-8a5f-988fb639ad2e1584×1417 102 KB

9

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

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

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

10

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

1 个赞
11

o，ok

12

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

13

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

1 个赞
14

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

15

按照老师说的改了还是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;
}
16

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

17

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

18

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

19

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

20

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