fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mod=1000000007;
  5. using ll = long long;
  6.  
  7. const int N=2020;
  8. char mp[N][N];
  9. int L[N][N];
  10. int R[N][N];
  11. int D[N][N];
  12. int U[N][N];
  13.  
  14. ll fpow(ll x, ll n)
  15. {
  16.     ll res=1;
  17.     for (;n;n>>=1) {
  18.         if (n&1) res=res*x%mod;
  19.         x=x*x%mod;
  20.     }
  21.     return res;
  22. }
  23.  
  24. int main()
  25. {
  26.     int n,m;
  27.     scanf("%d%d",&n,&m);
  28.     for (int i=1;i<=n;i++) {
  29.         scanf("%s",mp[i]+1);
  30.     }
  31.     ll ans=0;
  32.     int cnt=0;
  33.     for (int i=1;i<=n;i++) {
  34.         for (int j=1;j<=m;j++) {
  35.             if (mp[i][j]=='.') {
  36.                 ++cnt;
  37.                 L[i][j]=L[i][j-1];
  38.                 U[i][j]=U[i-1][j];
  39.             } else {
  40.                 L[i][j]=j;
  41.                 U[i][j]=i;
  42.             }
  43.         }
  44.     }
  45.     for (int i=n;i>=1;i--) R[i][m+1]=m+1;
  46.     for (int j=m;j>=1;j--) D[n+1][j]=n+1;
  47.     for (int i=n;i>=1;i--) {
  48.         for (int j=m;j>=1;j--) {
  49.             if (mp[i][j]=='.') {
  50.                 R[i][j]=R[i][j+1];
  51.                 D[i][j]=D[i+1][j];
  52.             } else {
  53.                 R[i][j]=j;
  54.                 D[i][j]=i;
  55.             }
  56.         }
  57.     }
  58.     for (int i=1;i<=n;i++) {
  59.         for (int j=1;j<=m;j++) if (mp[i][j]=='.') {
  60.             int c = (j-L[i][j]-1)
  61.                     +(i-U[i][j]-1)
  62.                     +(D[i][j]-i-1)
  63.                     +(R[i][j]-j-1)
  64.                     +1;
  65.             // printf("%d %d %d %d\n",L[i][j],U[i][j],R[i][j],D[i][j]);
  66.             // printf("%d %d %d %d\n",i,j,cnt,c);
  67.             ans += (fpow(2,cnt)-fpow(2,cnt-c))%mod;
  68.             ans %= mod;
  69.         }
  70.     }
  71.     if (ans<0) ans+=mod;
  72.     printf("%lld\n",ans);
  73.     return 0;
  74. }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
2 3
..#
#..
stdout
copy 
52
https://ideone.com/hzMlml
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!