【AtCoder - hhkb2020_e Lamp】想法dp-放灯泡问有多少地方被照亮

Problem Statement

We have a grid with H horizontal rows and W vertical columns of squares, where each square is tidy or untidy.

You will now place lamps on zero or more tidy squares in this grid.

A lamp will lighten the squares in each of the four directions - up, down, left, and right - to the point just before an edge of the grid or an untidy square is reached for the first time (the untidy square will not be lighted). The lamp will also lighten the square on which it is placed.

Given are integers HH, WW, and HH strings Si of length WW each. If the j-th character of Si is ., the square at the i-th row from the top and the j-th column from the left is tidy; if the j-th character of Si is #, the square at the i-th row from the top and the j-th column from the left is untidy.

Let KK be the number of tidy squares. There are 2K ways to place the lamps in total. Assume that, for each of these 2K ways, the number of squares lightened by one or more lamps is computed. Find the sum of those numbers modulo 1,000,000,007.

Constraints

• 1≤H≤20001≤H≤2000
• 1≤W≤20001≤W≤2000
• Si is a string of length W consisting of . and #.

Input

Input is given from Standard Input in the following format:

HH WW
S1S1
::
SHSH

Output

Print the sum, modulo 1,000,000,007, of the numbers of squares lightened by one or more lamps over the 2K ways to place the lamps.

Sample Input 1

1 5
..#..

Sample Output 1

48

There are 16 ways to place the lamps in total.

• In 9 of the ways (where at least one of the 1-st and 2-nd squares from the left contains a lamp and at least one of the 4-th and 5-th squares from the left contains a lamp), 4 squares will be lighted.
• In 3 of the ways (where at least one of the 1-st and 2-nd squares from the left contains a lamp but none of the 4-th and 5-th squares from the left contains a lamp), 2 squares will be lighted.
• In another 3 of the ways (where none of the 1-st and 2-nd squares from the left contains a lamp but at least one of the 4-th and 5-th squares from the left contains a lamp), 2 squares will be lighted.
• In 1 of the ways (where no square contains a lamp), 0 squares will be lighted.

The sum in question is 4×9+2×3+2×3+0×1=48.

Sample Input 2

2 3
..#
#..

Sample Output 2

52

传送门

题意

\(n*m\)的网格上，“.”表示干净的地方，“#”表示不干净的地方。假设有k个干净的地方，现在要在干净的地方放灯，总共有2^k种摆放方案，问每一种摆放方案中被照亮的位置数之和是多少？
一盏灯摆放在一个干净的位置上会向它的上下左右四个方向直射出去，直到碰到网格的边界或者碰到不干净的地方才会被挡住，不再射出去。被照射到的地方都是被点亮的。一个干净的位置摆放了灯的话，它自己这个位置也会被照亮。不干净的地方永远不会被照亮 。

题解

这道题如果从灯的角度去考虑能照亮多少块地方的话，去重非常困难，所以自然而然想到了转换一下角度，从每一块干净的地方这个角度去考虑。

• 考虑对于一块干净的地方，他怎么样才能被照亮，他被照亮
  • 要么是自身这个位置有放灯。
  • 要么是上下左右四个方向在碰到网格边界或者不干净的地方之前有某个位置放了灯

这样这块干净的地方才会被照亮。

• 再考虑如何计算方案数，上面列举出来的这些位置，只要有任意一个位置放了灯，该块干净的地方都能被照亮。
  假设这些位置的总数为num，整个网格里干净的总数为k，那么方案数就是\((2^{num}-1)*(2^{k-num})\)。

  首先num种可以使该干净的地方被照亮的位置，我从其中选出1，2，3，...，num种都能照亮这块地方，唯独不能不选，因此这num种选择的方案数就是\((2^{num}-1)\)，除了这num块以外，还有剩下k-num块，可以随意摆放，因此剩下k-num块的摆放方案数是\(2^{k-num}\)种。

  二者相乘就能求出对于一块干净的地方，他在多少种摆放方式里是被照亮的 。

• 还需要考虑的是如何快速处理出一个干净的格子上下左右延伸出去在遇到网格边界或者不干净的地方前总共有多少个格子。
  显然不能暴力地去做，否则就是n^3算法T到飞起。
  于是需要一点点预处理，用四个二维数组预先处理好每一个格子往上走在碰到障碍前有多少格子
  往下往左往右同理。
  用一点递推，拿往上举例，首先预处理好第一行，如果是“.”那\(ds[][]\)值置为1,否则置为0
  然后从第二行到第n行递推，对\(ds[i][j]\)来说，如果该位置上是不干净的，那么直接把\(ds[i][j]\)置为0
  否则\(ds[i][j]=ds[i-1][j]+1\)，这样递推维护即可，其他方向也是同理，只是方向转换一下而已。

坑点

这道题主要坑点是题意，很容易把题意读成一盏灯泡只能照亮上下左右和自己这5个格子，并且样例这样也能模过去

Code

/****************************
* Author : W.A.R            *
* Date : 2020-11-02-08:11   *
****************************/
/*
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define show(x) std:: cerr << #x << " = " << x << std::endl;
#define mem(a,x) memset(a,x,sizeof(a))
#define Rint register int
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int maxm=2e6+10;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double eps=1e-7;
ll qpow(ll a,ll n){a%=mod;ll ans=1;while(n){if(n%2)ans=ans*a%mod;n/=2;a=a*a%mod;}return ans;}
char s[2050][2050];
ll ds[2050][2050],dx[2050][2050],dz[2050][2050],dy[2050][2050];
int C(int n,int m){
	if(m>n)return 0;
	int ans=1;
	for(int i=1;i<=m;i++)ans*=n-i+1;
	for(int i=1;i<=m;i++)ans/=i;
	return ans;
}
ll n,m,K=0;
int check(int i,int j){
	if(s[i][j]=='#')return 0;
	ll ans=1;
	if(i-1>=0)ans+=ds[i-1][j];
	if(j-1>=0)ans+=dz[i][j-1];
	if(i+1<n)ans+=dx[i+1][j];
	if(j+1<m)ans+=dy[i][j+1];
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=0;i<n;i++)scanf("%s",s[i]);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(s[i][j]=='.')K++;
	for(int j=0;j<m;j++)ds[0][j]=(s[0][j]=='.');
	for(int i=1;i<n;i++)
		for(int j=0;j<m;j++)
			if(s[i][j]=='#')ds[i][j]=0;
			else ds[i][j]=ds[i-1][j]+1;
	for(int j=0;j<m;j++)dx[n-1][j]=(s[n-1][j]=='.');
	for(int i=n-2;i>=0;i--)
		for(int j=0;j<m;j++)
			if(s[i][j]=='#')dx[i][j]=0;
			else dx[i][j]=dx[i+1][j]+1;
	for(int i=0;i<n;i++)dz[i][0]=(s[i][0]=='.');
	for(int j=1;j<m;j++)
		for(int i=0;i<n;i++)
			if(s[i][j]=='#')dz[i][j]=0;
			else dz[i][j]=dz[i][j-1]+1;
	for(int i=0;i<n;i++)dy[i][m-1]=(s[i][m-1]=='.');
	for(int j=m-2;j>=0;j--)
		for(int i=0;i<n;i++)
			if(s[i][j]=='#')dy[i][j]=0;
			else dy[i][j]=dy[i][j+1]+1;
	ll ans=0;
	ll tmp=qpow(2,K);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int num=check(i,j);
			if(!num)continue;
			ans=(ans+((tmp-qpow(2,K-num)+mod)%mod))%mod;
		}
	}
	printf("%lld\n",ans%mod);
}