BFS广搜90ptsTLE一个点,求助,谢谢dalao!
查看原帖
BFS广搜90ptsTLE一个点,求助,谢谢dalao!
670355
Nuclear_Fish_cyq楼主2022/6/6 09:46

吸氧一个样,崩溃

#include <bits/stdc++.h>
using namespace std;
int n, m, level = 0, sum, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1}, sa, sb, ans, a[1000000];
struct point{
	int x, y, island_id;
	bool is_island, vis;
	bool check(){
		return x >= 0 && x < n && y >= 0 && y < n;
	}
}c[1000][1000], now, t;
queue <point>q;
/*void ready(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			c[i][j].vis = false;
		}
	}
}*/
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++){
		scanf("\n");
		for(int j = 0; j < n; j++){
	        c[i][j].x = i;
	        c[i][j].y = j;
	        c[i][j].vis = false;
			c[i][j].is_island = (bool)(getchar() - '0');
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
	        if(!c[i][j].vis){
	        	sum = 0;
	        	level++;
				c[i][j].island_id = level;
				t.island_id = level;
				q.push(c[i][j]);
	        	while(!q.empty()){
	        		now = q.front();
					q.pop();
					for(int i = 0; i < 4; i++){
						t = now;
						t.x += dx[i];
						t.y += dy[i];
						if(t.check() && !c[t.x][t.y].vis && c[t.x][t.y].is_island == !now.is_island){
							c[t.x][t.y].island_id = level;
							c[t.x][t.y].vis = true;
							q.push(c[t.x][t.y]);
							sum++;
						}
					}
				}
				a[level] = sum;
//				ready();
			}
		}
	}
	for(int i = 0; i < m; i++){
		ans = 0;
		scanf("%d%d", &sa, &sb);
		sa--;
		sb--;
		if(a[c[sa][sb].island_id] != 0){
			ans = a[c[sa][sb].island_id];
		}
		else{
			for(int j = 0; j < n; j++){
				for(int k = 0; k < n; k++){
					if(c[sa][sb].island_id == c[j][k].island_id){
						ans++;
					}
				}
			}
			a[c[sa][sb].island_id] = ans;	
		}
		printf("%d\n", ans);
	}
	return 0;
}

啊啊啊啊啊啊

2022/6/6 09:46
加载中...