bfs 80QAQ 哪里挂了
查看原帖
bfs 80QAQ 哪里挂了
542905
WannaYellow楼主2022/7/29 20:44
#include<bits/stdc++.h>
#define int long long
using std::cin;
using std::cout;
using std::endl;
std::vector<std::pair<int,int> > v[105][105];
std::queue<std::pair<int,int> > q;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int ans=1,n,m;
int lvis[105][105],vis[105][105];
void bfs(){
	q.push(std::make_pair(1,1));
	while(!q.empty()){
		std::pair<int,int> tp=q.front();
		q.pop();
		if(vis[tp.first][tp.second])continue;
		vis[tp.first][tp.second]=1;
		for(auto t : v[tp.first][tp.second]){
			if(!lvis[t.first][t.second]){
				lvis[t.first][t.second]=1;
				ans++;
				for(int i=0;i<4;i++){
					int nx=t.first+dx[i],ny=t.second+dy[i];
					if(vis[nx][ny]){
						q.push(t);
						break;
					}
				}
			}
		}
		for(int i=0;i<4;i++){
			int nx=tp.first+dx[i],ny=tp.second+dy[i];
			if(nx>0&&nx<=n&&ny>0&&ny<=n&&lvis[nx][ny]){
				q.push(std::make_pair(nx,ny));
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		v[x1][y1].push_back(std::make_pair(x2,y2));
	}
	bfs();
	cout<<ans;
	return 0;
}
2022/7/29 20:44
加载中...