解题报告

这一题的题意很好理解

即如果输入为，表示这个格子不能到达这个格子

我们要是用一个四维数组存储的话，可行是可行，但并不是最优的方案

我们可以把整个图看成有个点的无向图，每个点向它周围四个点连边，统计出每一个联通块有多少点，然后用乘法原理做即可

这里提供一种题解里没有的，用迭代器删边来减少占用的做法

具体实现请看代码

//Copyright (c) 2019 by xiao_mmQF. All Rights Reserved.
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define inl inline
#define reg register
#define db long double
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
inl int read(){ int x=0,f=0; char ch=0; while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar(); return f?-x:x; }
inl void Ot(reg int x) { if(x<0)putchar('-'),x=-x; if(x>=10)Ot(x/10); putchar(x%10+'0'); }
inl void Print(reg int x,char til='\n'){Ot(x);putchar(til);}
inl int Max(reg int x,reg int y){return x>y?x:y;}
inl int Min(reg int x,reg int y){return x<y?x:y;}
inl int Abs(reg int x){return x<0?-x:x;}

const int MAXN=10010;

int n,k,r,ans;
int tot,pos[MAXN];
bool mark[MAXN],is[MAXN];
vector<int>G[MAXN];

#define It vector<int>::iterator

int get(int r,int c){return (r-1)*n+c;}
//得到第r行第c列的点的编号

void del(int x,int y){
    for(It iter=G[x].begin();iter!=G[x].end();iter++)
        if(*iter==y){G[x].erase(iter);break;}
}
//删边操作

int bfs(int x){
    int tmp=0;
    queue<int>que;
    que.push(x);
    mark[x]=1;
    while(!que.empty()){
        int h=que.front();
        que.pop();
        if(is[h])tmp++;
        for(It iter=G[h].begin();iter!=G[h].end();iter++){//迭代器真好用.jpg
            int to=*iter;
            if(!mark[to])mark[to]=1,que.push(to);
        }
    }
    return tmp;
}
//简单的bfs染色

signed main() {
    n=read(),k=read(),r=read();
    for(reg int i=1;i<=n;i++)
        for(reg int j=1;j<=n;j++){
            if(i-1>0)
                G[get(i,j)].push_back(get(i-1,j));
            if(j-1>0)
                G[get(i,j)].push_back(get(i,j-1));
            if(i+1<=n)
                G[get(i,j)].push_back(get(i+1,j));
            if(j+1<=n)
                G[get(i,j)].push_back(get(i,j+1));
        }

        //向自己周围四个点连边

    for(reg int i=1;i<=r;i++){
        int p=read(),q=read(),x=read(),y=read();
        del(get(p,q),get(x,y));
        del(get(x,y),get(p,q));
    }
    //删边操作，因为是双向的所以要删两次

    for(reg int i=1;i<=k;i++){
        int p=read(),q=read();
        is[pos[i]=get(p,q)]=1;
    }

    for(reg int i=1;i<=k;i++){
        if(!mark[pos[i]]){
            int k=bfs(pos[i]);
            ans+=k*tot;
            tot+=k;
            //乘法原理计算
        }
    }

    Print(ans);

    return 0 ;
}