看题解都是dfs我看一下地图就写了个bfs才40分来个大佬看看
  • 板块P1605 迷宫
  • 楼主wh_1024
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/8/10 17:36
  • 上次更新2023/10/27 16:05:03
查看原帖
看题解都是dfs我看一下地图就写了个bfs才40分来个大佬看看
648053
wh_1024楼主2022/8/10 17:36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define f(i,j,n) for(int i=j;i<=n;i++)
const ll mx=1e12,mi=-1e12,N=10000000;
int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
int n,m,t,qx,qy,zx,zy,ma[10][10],fx,fy,ans=0,vis[10][10];
int main(){
	cin>>n>>m>>t;
	cin>>qx>>qy>>zx>>zy;
	memset(ma,0,sizeof(ma));
	memset(vis,0,sizeof(vis))
	f(i,1,t){
		cin>>fx>>fy;
		ma[fx][fy]=1;
	}
	queue<int> q[2];
	vis[qx][qy]=1;
	q[0].push(qx);q[1].push(qy);
	while(!q[0].empty())
	{
		int x=q[0].front(),y=q[1].front();
		if(x==zx&&y==zy)ans++;
		q[0].pop(),q[1].pop();
		f(i,1,4){
			if(ma[x+dx[i]][y+dy[i]]==0&&x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&!vis[x+dx[i]][y+dy[i]])
			{
				int xx=x+dx[i],yy=y+dy[i];
				q[0].push(xx);q[1].push(yy);
				vis[xx][yy]=1;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
2022/8/10 17:36
加载中...