C++14(g++5.4) 解法, 执行用时: 35ms, 内存消耗: 38752K, 提交时间: 2019-09-27 10:38:55

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=11000;
int a[maxn*maxn];
int col[maxn*maxn],color;
int n,k,r;
bool cut[maxn][maxn];
int ans;

int get_num(int x,int y)
{
    return (x-1)*n+y;//用下标取出每个点的编号
}

int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};

bool check(int x,int y)
{
    if(x>=1&&y>=1&&x<=n&&y<=n)return 1;
    return 0;
}

void bfs(int x,int y)
{
    color++;
    queue<int>q1,q2;
    q1.push(x);q2.push(y);
    while(!q1.empty())
    {
        int u=get_num(q1.front(),q2.front());
        col[u]=color;
        for(int i=0;i<4;i++)
        {
            int xx=q1.front()+dx[i];
            int yy=q2.front()+dy[i];
            int v=get_num(xx,yy);
            if(check(xx,yy)&&!cut[u][v]&&!cut[v][u]&&!col[v])//转移时用cut数组判断
            {
                q1.push(xx);q2.push(yy);
                col[v]=color;
            }
        }q1.pop();q2.pop();
    }
}

int main()
{
    scanf("%d%d%d",&n,&k,&r);
    for(int i=1;i<=r;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int num1=get_num(x1,y1);
        int num2=get_num(x2,y2);
        cut[num1][num2]=cut[num2][num1]=1;
    }
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]=get_num(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!col[get_num(i,j)])
            {
                bfs(i,j);
            }
        }
    }
    for(int i=1;i<k;i++)
    {
        for(int j=i+1;j<=k;j++)
        {
            if(col[a[i]]!=col[a[j]])ans++;
        }
    }cout<<ans;

}

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 376K, 提交时间: 2020-11-28 09:48:27

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=105;

int sum, num, answer;
int n, k, r, rr, c, r1, c1, ans[N*N];
bool cow[N][N], ltk[N][N], a[N][N][4];
int stepx[4]={0, 1, 0, -1};
int stepy[4]={1, 0, -1, 0};

void dfs(int x, int y){
	//printf("%d %d\n", x, y);
	if(ltk[x][y]||x<1||x>n||y<1||y>n) return ;
	if(cow[x][y])++sum;
	ltk[x][y]=true;
	for (int i=0;i<4;++i){
		if(a[x][y][i]) continue;
		int xx=x+stepx[i];
		int yy=y+stepy[i];
		if(!ltk[xx][yy]) dfs(xx, yy);
	}
}

int main (){
	scanf ("%d%d%d", &n, &k, &rr);
	for (int i=1;i<=rr;++i){
		scanf ("%d%d%d%d", &r, &c, &r1, &c1);
		if(r==r1){
			a[r][min(c, c1)][0]=1;
			a[r][max(c, c1)][2]=1;
		}else{
			a[min(r, r1)][c][1]=1;
			a[max(r, r1)][c][3]=1;
		}
	}for(int i=1;i<=k;++i){
		scanf ("%d%d", &r, &c);
		cow[r][c]=true;
	}for(int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			if(!ltk[i][j]){
				sum=0;
				dfs(i, j);
				if(sum)	ans[++num]=sum;
			}
	for (int i=1;i<num;++i)
		for (int j=i+1;j<=num;++j)
			answer+=ans[i]*ans[j];
	printf("%d\n", answer);
	
	return 0;
}