50分求助(bfs)
  • 板块P1605 迷宫
  • 楼主cille
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/20 19:08
  • 上次更新2024/7/20 20:19:21
查看原帖
50分求助(bfs)
1396981
cille楼主2024/7/20 19:08
#include <iostream>
#include <queue>
using namespace std;
const int dx[105]={-1,1,0,0};
const int dy[105]={0,0,-1,1};
int vis[105][1005],a[105][105];
int sx,sy,ex,ey,num,n,m,ans=0;
struct node{
	int x,y;
}barrier[105];
void bfs(int x,int y){
	queue<node> q;
	node s;
	s.x=x,s.y=y;
	q.push(s);
	vis[x][y]=1;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int nx=t.x+dx[i];
			int ny=t.y+dy[i];
			if(nx>n||nx<1||ny>m||ny<1||vis[nx][ny]==1||a[nx][ny]==0) continue;
			if(nx==ex && ny==ey){
				ans++;continue;
			} 
			node tmp;
			tmp.x=nx,tmp.y=ny;
			q.push(tmp);
			vis[nx][ny]=1;
		} 
	}	
} 
int main(){
	cin>>n>>m>>num;
	cin>>sx>>sy>>ex>>ey;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=true;
		}
	}
	for(int i=1;i<=num;i++){
		int x,y;
		cin>>x>>y;
		a[x][y]=0;
	}
	bfs(sx,sy);
	cout<<ans;
	return 0;
}
2024/7/20 19:08
加载中...