用了连通图仍然超时的代码 蒟蒻求助
  • 板块P1141 01迷宫
  • 楼主EllinY
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/8/18 14:07
  • 上次更新2023/10/27 14:47:34
查看原帖
用了连通图仍然超时的代码 蒟蒻求助
514936
EllinY楼主2022/8/18 14:07

80pnts TLE HELP

#include<bits/stdc++.h>
using namespace std;
int n,m,f,b,id;//f:队首  b:队尾  id:连通块编号 
int x,y,xx,yy;//输入的  xx和 yy后面会用来简化代码 
int vis[1001][1001];//连通图标记,同一个数为同一个连通块 
int ans[1000001];//记录每个连通块的格子数,以连通块编号做下标 
bool mp[1001][1001];//01迷宫的地图 
int a[1000001][2];//模拟队列 
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};//四方向移动 
void bfs(){
	id++;//准备开一个新连通块 
	vis[x][y]=id;//标记第一个点所属的连通块 
	b++;//队尾加一(b从0开始,所以先加再往队尾放数值) 
	a[b][0]=x;
	a[b][1]=y;//把第一个点塞进队列 
	ans[id]++;//此连通块的方格数加一 
	while(f<=b){
		for(int i=0;i<4;i++){
			xx=a[f][0]+dx[i];
			yy=a[f][1]+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&
			   vis[xx][yy]==0&&mp[xx][yy]==!mp[a[f][0]][a[f][1]]){
			//保证不越界,不重复标记,两点之间可以走(一个 0一个 1) 
				vis[xx][yy]=id;
				b++;
				a[b][0]=xx;
				a[b][1]=yy;
				ans[id]++;
				//跟处理第一个点的方法一样 
			} 
		}
		f++;
		//把这个点能走到的地方都枚举完了,就把它踢出队列(队首加一) 
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char ch;
			cin>>ch;
			mp[i][j]=ch-'0';
		}
	}//读入 
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		if(vis[x][y]==0){
			memset(a,0,sizeof(a));
			f=1,b=0;
			bfs();
		}//没标记过就把此点所在的连通块标记好 
		printf("%d\n",ans[vis[x][y]]);
		//取出此点所在的连通块的编号,找到答案 
	}
	return 0;
}

感谢Thanks♪(・ω・)ノ

2022/8/18 14:07
加载中...