液体史莱姆

描述

众所周知，史莱姆是一种液体。生物学家通过多年对史莱姆习性的研究发现：当史莱姆进入一种器皿时，它们总会选择一个尽可能低的身位。更准确地说，它们会选择一个身位，使得它们身体最高点的高度尽可能低。

给定一个n行m列的器皿，共n×m个格子，从上到下被标记为第1行到第n行，第1行最高，第n行最低，每个格子要么可以通行，要么不可通行。

史莱姆是一种会占据k个可通行格子的生物，请注意这k个格子要是连通的，两个格子连通当且仅当它们具有公共边。

请你利用计算机编程来模拟史莱姆这种生物的行为。

输入

第一行包含一个正整数T(1≤T≤10)，表示测试数据的组数。

每组数据第一行包含三个整数 n,m,k(1≤n,m≤1000,1≤k≤10^6)。 接下来n行，每行一个长度为m的字符串，依次描述器皿的第1行,第2行,...,第n行。一个格子如果是#，则不能通行；如果是.，则可以通行。

输出

对于每组数据输出一行，即史莱姆身体最高点位于哪一行。

若这个器皿放不下史莱姆，输出−1

#include<bits/stdc++.h>
#define F(i,a,b,c) for(int i=a;i<=b;i+=c)
using namespace std;
int n,m,k,t,vis[1001][1001],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[1001][1001];
struct node {
	int x,y;
};
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
bool bfs(int h) {
//	cout<<h<<endl;
	memset(vis,0,sizeof(vis));
	node cur,nxt;
	F(j,0,m-1,1) {
		if(vis[h][j]||a[h][j]=='#')continue;
		int ans=0;
		queue<node>q;
		cur.x=h;
		cur.y=j;
		q.push(cur);
		vis[cur.x][cur.y]=1;
		while(!q.empty()) {
			cur=q.front();
			q.pop();
//			cout<<cur.x<<" "<<cur.y<<endl;
			ans++;
			F(i,0,3,1) {
				nxt.x=cur.x+dir[i][0];
				nxt.y=cur.y+dir[i][1];
				if(nxt.x<h||nxt.x>n||nxt.y<0||nxt.y==m||vis[nxt.x][nxt.y]||a[nxt.x][nxt.y]=='#')continue;
				q.push(nxt);
				vis[nxt.x][nxt.y]=1;
			}
		}
		if(ans>=k)return true;
	}
	return false;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	t=read();
	while(t--) {
		n=read();
		m=read();
		k=read();
		F(i,1,n,1) {
			scanf("%s",a[i]);
		}
		if(!bfs(1))cout<<-1<<endl;
		else {
			int l=1,r=n;
			while(l<r) {
//				cout<<l<<"      "<<r<<endl;
				int mid=(l+r)>>1;
				if(bfs(mid))l=mid+1;
				else r=mid-1;
			}
			if(bfs(l))cout<<l<<endl;
			else cout<<l-1<<endl;
		}
	}
	return 0;
}