HDU 5652 India and China Origins

二分答案+验证,注意一开始就不连通的话输出0

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=+;
char s[maxn][maxn];
char tmp[maxn][maxn];
bool flag[maxn][maxn];
int dir[][]={
{,},
{,-},
{,},
{-,}
}; struct X
{
int x,y;
}q[maxn*maxn];
int n,m,Q; void read()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) scanf("%s",s[i]);
scanf("%d",&Q);
for(int i=;i<=Q;i++) scanf("%d%d",&q[i].x,&q[i].y);
} bool P(int a,int b)
{
if(a>=&&a<n)
{
if(b>=&&b<m)
{
if(tmp[a][b]=='')
{
if(flag[a][b]==)
{
return ;
}
}
}
}
return ;
} void dfs(int x,int y)
{
flag[x][y]=;
for(int i=;i<;i++)
{
int newx=x+dir[i][];
int newy=y+dir[i][];
if(P(newx,newy)) dfs(newx,newy);
}
} bool f(int year)
{
for(int i=;i<n;i++)
for(int j=;j<m;j++)
tmp[i][j]=s[i][j]; for(int i=;i<=year;i++) tmp[q[i].x][q[i].y]=''; bool fail=;
for(int j=;j<m;j++) if(tmp[][j]=='') fail=;
if(fail) return ; fail=;
for(int j=;j<m;j++) if(tmp[n-][j]=='') fail=;
if(fail) return ; memset(flag,,sizeof flag);
for(int j=;j<m;j++)
if(tmp[][j]=='')
dfs(,j); fail=;
for(int j=;j<m;j++)
if(tmp[n-][j]==''&&flag[n-][j]==) fail=;
return fail;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
read();
if(f()) printf("0\n");
else
{
int ans=-;
int left=,right=Q;
while(left<=right)
{
int mid=(left+right)/;
if(f(mid))
{
ans=mid;
right=mid-;
}
else
{
left=mid+;
}
}
printf("%d\n",ans);
}
}
return ;
}
上一篇:Nginx 反向代理接收用户包体方式


下一篇:刚開始学习的人非常有用:纯struts框架实现用户登陆