这一题的题意很好理解
即如果输入为,表示这个格子不能到达这个格子
我们要是用一个四维数组存储的话,可行是可行,但并不是最优的方案
我们可以把整个图看成有个点的无向图,每个点向它周围四个点连边,统计出每一个联通块有多少点,然后用乘法原理做即可
这里提供一种题解里没有的,用迭代器删边来减少占用的做法
具体实现请看代码
//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 ; }