很强的题。
结论：每个非 \(0\) 点的值一定是它到最近的 \(0\) 的距离。
证明：记该点值为 \(x\)，上文距离为 \(d\)。考虑反证。
- 若 \(x>d\)。
考虑该点到 \(0\) 的最短路。记路径上的点到该点的距离为 \(d'\)，值为 \(x'\)。则 \(x'\) 最小能取到 \(x-d'\)。而与 \(0\) 相邻的点最小只能取到 \(x-(d-1)=x-d+1>1\)。不符合条件。
- 若 \(x<d\)。
则一定有一个与它相邻的点值为 \(x-1\)，再与这个点相邻的一定有一个 \(x-2\)。以此类推。则一定有一个与该点距离为 \(x\) 的点为 \(0\)。不符合条件。
综上，结论得证。
所以先钦定若干个未知的点为 \(0\)，剩下便以确定。
还有 corner case：\(0\) 的数量 \(=0\) 时无解。考虑最小值的四周不会有比它更小的数即可。
综上，答案即为 \(2^{cnt}-[cnt=n\times m]\)。其中 \(cnt\) 为初始非 \(0\) 点个数。
code：
点击查看代码
int n,m;
char s[N];
inline int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)
ret=1ll*ret*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return ret;
}
void Yorushika(){
scanf("%d%d",&n,&m);
int cnt=0;
rep(i,1,n){
scanf("%s",s+1);
rep(j,1,m){
cnt+=s[j]=='#';
}
}
printf("%d\n",qpow(2,cnt)-(cnt==n*m));
}
signed main(){
int t=1;
scanf("%d",&t);
while(t--)
Yorushika();
}