RT

采用广搜，#2TLE

90分评测记录

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

int fx[4] = {0,1,0,-1};
int fy[4] = {1,0,-1,0};
int N;
map<pair<int,int>, int> vist;
map<pair<int,int>, int> grass;
int x,y;
int maxx,maxy;
int minx = 1e6, miny = 1e6;
long long Answer;

void BFS()
{
	queue<pair<int,int> > Q;
	while(!Q.empty()) Q.pop();
	Q.push({maxx, maxy}); 
	while(!Q.empty()) {
		int X = Q.front().first;
		int Y = Q.front().second;
		Q.pop();
		
		if(X < minx || X > maxx || Y < miny || Y > maxy || vist[{X,Y}] != 0 || grass[{X,Y}] != 0)
			continue;
		vist[{X,Y}] = 1;
		for(int i = 0 ; i< 4 ; i++) {
			x = X+fx[i];
			y = Y+fy[i];
			if(grass[{x,y}] != 0) {
				Answer++;
			}
			if(x < -1 || x > maxx || y < -1 || y > maxy || vist[{x,y}] != 0 || grass[{x,y}] != 0) {
				continue;
			} else {
				Q.push({x,y});
			}
		}
	}
}

int main()
{
	freopen("girth.in","r",stdin);
	freopen("girth.out","w",stdout); 
	scanf("%d", &N);
	for(int i = 1 ; i<= N ; i++) {
		scanf("%d%d", &x, &y);
		grass[{x,y}] = 1;
		maxx = max(maxx,x);
		maxy = max(maxy,y);
		minx = min(minx,x);
		miny = min(miny,y);
	}
	minx--;
	miny--;
	maxx++;
	maxy++;
	BFS();
	printf("%d\n", Answer);
	fclose(stdin);
	fclose(stdout);
	return 0;
}