HDU 5652 India and China Origins 二分优化+BFS剪枝

时间:2021-12-23 22:34:24

题目大意:给你一个地图0代表可以通过1代表不可以通过。只要能从第一行走到最后一行,那么中国与印度是可以联通的。现在给你q个点,每年风沙会按顺序侵蚀这个点,使改点不可通过。问几年后中国与印度不连通。若一直联通输出-1.

题目思路:看数据这道题就是卡时间的,我们的基本思路是每当风沙侵蚀一个点,我们就进行一次广搜,看看图上下是否联通,我们应尽可能的去优化这个过程。

所以我们可以在遍历年的时候用二分查找:

若当年图可以上下联通,则继续向右查找

若当年图上下无法联通,则向左查找

剪枝:

为了省时间我们应该剪去一些不必要走的路径:假设第一行的x点在第n年已经不可达到最后一行,那么我们就标记一下,在m(m>n)年时,不对x点经行广搜。

具体看代码:

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 1000005
#define mod 1000000007 using namespace std;
struct node
{
int x,y;
};
char Map[][];
int vis[][],n,m,q,a[MAX],b[MAX],book[MAX],v[][]= {{,},{-,},{,},{,-}},Stack[MAX]; int check(int x,int y)
{
if(x>= && x<n && y>= && y<m && !vis[x][y] && Map[x][y]=='')
return ;
return ;
} int BFS(int x,int y)
{
vis[x][y]=;
node now,next;
now.x=x;
now.y=y;
queue<node>Q;
Q.push(now);
while(!Q.empty())
{
now=Q.front();
Q.pop();
if(now.x==n-)
{
return ;
}
for(int i=; i<; i++)
{
next.x=now.x+v[i][];
next.y=now.y+v[i][];
if(check(next.x,next.y))
{
vis[next.x][next.y]=;
Q.push(next);
}
}
}
return ;
} int main()
{
int T,i,j,ans,ok1,ok2,ok,L,R,top;
scanf("%d",&T);
while(T--)
{
ok1=;//记录第一行是否有可行点
ok2=;//记录第二行是否有可行点
ok=;
scanf("%d%d",&n,&m);
for(i=; i<n; i++)
scanf("%s",Map[i]);
scanf("%d",&q);
for(i=; i<=q; i++)
scanf("%d%d",&a[i],&b[i]);
for(i=; i<m; i++)
{
if(Map[][i]=='')
ok1=;
if(Map[n-][i]=='')
ok2=;
}
if(ok1 && ok2)
ok=;
if(!ok)//若第一行或最后一行无可行点,直接输出0
{
printf("0\n");
continue;
}
ans=;
L=;
R=q;
memset(book,,sizeof(book));//记录第一行被剪去的点
while(R>L)//二分查找年份
{
top=;
int mid=L+(R-L)/;
for(i=; i<=mid; i++)//当前为mid年,更新地图被侵蚀的点
{
int x=a[i];
int y=b[i];
Map[x][y]='';
}
ok=;
for(i=; i<m; i++)
{
if(Map[][i]=='' && !book[i])
{
memset(vis,,sizeof(vis));
ok=BFS(,i);
if(ok)//当年图上下可连通
break;
else
{
Stack[++top]=i;//若该点无法到达最后一行,记录改点为可能要被剪去的点
}
}
} if(ok)
{
L=mid+;
ans=max(ans,mid);
for(j=; j<=top; j++)//剪枝
{
int num=Stack[j];
book[num]=;
}
top=;
}
else
{
R=mid;
} for(i=; i<=mid; i++)//还原地图
{
int x=a[i];
int y=b[i];
Map[x][y]='';
}
} ok=;
for(i=; i<=L; i++)
{
int x=a[i];
int y=b[i];
Map[x][y]='';
}
for(i=; i<m; i++)
{
if(Map[][i]=='' && !book[i])
{
memset(vis,,sizeof(vis));
ok=BFS(,i);
if(ok)
break;
else
{
Stack[++top]=i;
}
}
}
if(ok)
ans=L; if(ans == q)
ans=-;
else
ans++;
printf("%d\n",ans);
}
return ;
}