自动搬运

查看原文

来自洛谷，原作者为

	Annam 本人只是个蒟蒻

搬运于2025-08-24 21:51:22，当前版本为作者最后更新于2019-12-14 00:53:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻的第五篇题解

目录

1.思路

2.代码

一.思路

关于每个格子是否有道路相隔可以那一个三维数组记一下，这题跟P1457 城堡 The Castle比较像

之后再把牛的方位记一下

然后用dfs染色，最后统计每个连通块上的牛的个数，最后在把他们两两相乘的积相加得出答案

二.代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,k;
int road;
int a[105][105][4];//北东西南 
int color[105][105];
int b[105][105];
int x,y,x1,y1;
int num;
int all;
long long ans;
vector<int> area;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};//北东西南 
void dfs(int x,int y)
{
	if(x<1||y<1||x>n||y>n){
		return;
	}
	if(color[x][y]!=-1){
		return;
	}
    color[x][y]=num;	
	if(b[x][y]==1){
		all++;
	}
	for(int i=0;i<4;i++){
		if(a[x][y][i]==1){
			continue;
		}
		int xx=x+dx[i];
		int yy=y+dy[i];
		dfs(xx,yy);
	}
}
int main()
{
	cin>>n>>k>>road;
	for(int i=1;i<=road;i++){
		cin>>x>>y>>x1>>y1;
		if(x==x1){
			a[x][min(y,y1)][1]=1;
			a[x][max(y,y1)][3]=1;
		}else{
			a[min(x,x1)][y][2]=1;
			a[max(x,x1)][y][0]=1;
		}
	}
	for(int i=1;i<=k;i++){
		cin>>x>>y;
		b[x][y]=1;
	}
	area.push_back(0);
	memset(color,-1,sizeof(color));
	for(int i=1;i<=n;i++){
		for(int i1=1;i1<=n;i1++){
			if(color[i][i1]==-1){
				all=0;
				num++;
				dfs(i,i1);
				area.push_back(all);
			}
		}
	}
	for(int i=1;i<num;i++){
		for(int i1=i+1;i1<=num;i1++){
			ans+=area[i]*area[i1];
		}
	}
	cout<<ans;
	return 0;
}

莫抄袭，没了AC记录，空悲切