考虑将最上中最左的跳蚤孤立, 容易发现他的上面和左面没有跳蚤, 因此只需要将他的右边和下边替换掉就可以了
答案为 - 1 有两种情况: 1.c>=n*m-1;2.c=n*m-2 且这两只跳蚤相邻
对于其他情况, 将所有跳蚤建图后判断: 1. 是否有多个连通块; 2. 是否有割点即可, 由于跳蚤数量很多, 容易发现只需要选择周围 5*5 的范围内有蛐蛐的跳蚤建图即可
只选择 3*3 会有反例 (以下 q 表示蛐蛐, t 表示跳蚤):
- ttttt
- tttqt
- ttttt
- tqttt
- ttttt
- (注意如果 c=0 那么答案为 ((n>1)&&(m>1))+1)
- #include<bits/stdc++.h>
- using namespace std;
- #define N 100005
- #define mp make_pair
- #define pii pair<int,int>
- struct ji{
- int nex,to;
- }edge[N<<5];
- queue<pii>q;
- map<pii ,int>a,mat;
- int t,n,m,k,x[N],y[N],tx[4]={-1,0,0,1},ty[4]={0,-1,1,0};
- int V,E,head[N<<2],vis[N<<2],dfn[N<<2],low[N<<2],sum[N<<2];
- void add(int x,int y){
- edge[E].nex=head[x];
- edge[E].to=y;
- head[x]=E++;
- }
- void dfs(int k,int fa){
- low[k]=dfn[k]=++dfn[0];
- for(int i=head[k];i!=-1;i=edge[i].nex)
- if (edge[i].to!=fa)
- if (dfn[edge[i].to])low[k]=min(low[k],dfn[edge[i].to]);
- else{
- dfs(edge[i].to,k);
- low[k]=min(low[k],low[edge[i].to]);
- if (dfn[k]<=low[edge[i].to])sum[k]++;
- }
- }
- int bfs(int x,int y){
- a.clear();
- mat[mp(x,y)]=2;
- q.push(mp(x,y));
- for(int i=1;i<=V;i++)vis[i]=dfn[i]=sum[i]=0;
- V=E=dfn[0]=0;
- while (!q.empty()){
- x=q.front().first;
- y=q.front().second;
- q.pop();
- for(int dx=-2;dx<3;dx++)
- for(int dy=-2;dy<3;dy++){
- if ((x+dx<1)||(y+dy<1)||(x+dx>n)||(y+dy>m))continue;
- pii o=mp(x+dx,y+dy);
- if (mat[o]==1){
- mat[o]=2;
- q.push(o);
- }
- if (mat[o]==2)continue;
- if (!a[o]){
- a[o]=++V;
- head[V]=-1;
- for(int dz=0;dz<4;dz++){
- int p=a[mp(x+dx+tx[dz],y+dy+ty[dz])];
- if (p){
- add(V,p);
- add(p,V);
- }
- }
- }
- if (a[o]>0)vis[a[o]]|=((-2<dx)&&(dx<2)&&(-2<dy)&&(dy<2));
- }
- }
- dfs(1,0);
- if (dfn[0]<V)return 0;
- if ((vis[1])&&(sum[1]>1))return 1;
- for(int i=2;i<=V;i++)
- if ((vis[i])&&(sum[i]))return 1;
- return 2;
- }
- int main(){
- scanf("%d",&t);
- memset(head,-1,sizeof(head));
- while (t--){
- scanf("%d%d%d",&n,&m,&k);
- if (k>=1LL*n*m-1){
- for(int i=1;i<=k;i++)scanf("%*d%*d");
- printf("-1\n");
- continue;
- }
- mat.clear();
- for(int i=1;i<=k;i++){
- scanf("%d%d",&x[i],&y[i]);
- mat[mp(x[i],y[i])]=1;
- }
- int ans=2;
- for(int i=1;i<=k;i++)
- if (mat[mp(x[i],y[i])]==1)ans=min(ans,bfs(x[i],y[i]));
- if (((n==1)||(m==1))&&(ans))ans=1;
- if ((1LL*n*m-2==k)&&(ans))ans=-1;
- printf("%d\n",ans);
- }
- }
- View Code
[bzoj4651] 网格
来源: http://www.bubuko.com/infodetail-3332449.html