#include<cstdio> #include<algorithm> #define f first #define s second #define mp make_pair using namespace std; pair <bool,bool> t[3009][3009]; int main() { int n,k; char c; scanf ("%d %d", &n, &k); for (int i=2; i<=n+1; i++) { for (int j=2; j<=n+1; j++) { scanf (" %c", &c); if (c=='#') t[i][j]=mp(1,0); else t[i][j]=mp(0,0); } } for (int i=0; i<=n+3; i++) { t[i][0]=mp(0,1); t[i][n+3]=mp(0,1); t[0][i]=mp(0,1); t[n+3][i]=mp(0,1); t[i][1]=mp(0,1); t[i][n+2]=mp(0,1); t[1][i]=mp(0,1); t[n+2][i]=mp(0,1); } long long wyn=0; for (int i=2; i<=n+1; i++) { for (int j=2; j<=n+1; j++) { if (t[i][j].f==1) { if (t[i+1][j].f==0&&t[i+1][j].s==0) { wyn++; t[i+1][j].s=1; } if (t[i-1][j].f==0&&t[i-1][j].s==0) { wyn++; t[i-1][j].s=1; } if (t[i][j+1].f==0&&t[i][j+1].s==0) { wyn++; t[i][j+1].s=1; } if (t[i][j-1].f==0&&t[i][j-1].s==0) { wyn++; t[i][j-1].s=1; } } } } if (k==1) printf ("%lld", wyn); else { wyn*=wyn-1; wyn/=2; //printf ("%lld", wyn); wyn%=1000000007; for (int i=2; i<=n+1; i++) { for (int j=2; j<=n+1; j++) { if (t[i][j].f==0) { if (t[i-1][j].f==0&&t[i+1][j].f==0&&t[i][j-1].f==0&&t[i][j+1].f==0) { if (t[i-2][j].f==1) wyn++; if (t[i+2][j].f==1) wyn++; if (t[i][j+2].f==1) wyn++; if (t[i][j-2].f==1) wyn++; if (t[i-1][j-1].f==1&&t[i-2][j].f!=1) wyn++; if (t[i-1][j-1].f==1&&t[i][j-2].f!=1) wyn++; if (t[i+1][j+1].f==1&&t[i+2][j].f!=1) wyn++; if (t[i+1][j+1].f==1&&t[i][j+2].f!=1) wyn++; if (t[i+1][j-1].f==1&&t[i+2][j].f!=1&&t[i+1][j+1].f!=1) wyn++; if (t[i+1][j-1].f==1&&t[i][j-2].f!=1&&t[i-1][j-1].f!=1) wyn++; if (t[i-1][j+1].f==1&&t[i-2][j].f!=1&&t[i-1][j-1].f!=1) wyn++; if (t[i-1][j+1].f==1&&t[i][j+2].f!=1&&t[i+1][j+1].f!=1) wyn++; wyn%=1000000007; } //printf ("%lld ", wyn); } } } printf ("%lld", wyn); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include<cstdio> #include<algorithm> #define f first #define s second #define mp make_pair using namespace std; pair <bool,bool> t[3009][3009]; int main() { int n,k; char c; scanf ("%d %d", &n, &k); for (int i=2; i<=n+1; i++) { for (int j=2; j<=n+1; j++) { scanf (" %c", &c); if (c=='#') t[i][j]=mp(1,0); else t[i][j]=mp(0,0); } } for (int i=0; i<=n+3; i++) { t[i][0]=mp(0,1); t[i][n+3]=mp(0,1); t[0][i]=mp(0,1); t[n+3][i]=mp(0,1); t[i][1]=mp(0,1); t[i][n+2]=mp(0,1); t[1][i]=mp(0,1); t[n+2][i]=mp(0,1); } long long wyn=0; for (int i=2; i<=n+1; i++) { for (int j=2; j<=n+1; j++) { if (t[i][j].f==1) { if (t[i+1][j].f==0&&t[i+1][j].s==0) { wyn++; t[i+1][j].s=1; } if (t[i-1][j].f==0&&t[i-1][j].s==0) { wyn++; t[i-1][j].s=1; } if (t[i][j+1].f==0&&t[i][j+1].s==0) { wyn++; t[i][j+1].s=1; } if (t[i][j-1].f==0&&t[i][j-1].s==0) { wyn++; t[i][j-1].s=1; } } } } if (k==1) printf ("%lld", wyn); else { wyn*=wyn-1; wyn/=2; //printf ("%lld", wyn); wyn%=1000000007; for (int i=2; i<=n+1; i++) { for (int j=2; j<=n+1; j++) { if (t[i][j].f==0) { if (t[i-1][j].f==0&&t[i+1][j].f==0&&t[i][j-1].f==0&&t[i][j+1].f==0) { if (t[i-2][j].f==1) wyn++; if (t[i+2][j].f==1) wyn++; if (t[i][j+2].f==1) wyn++; if (t[i][j-2].f==1) wyn++; if (t[i-1][j-1].f==1&&t[i-2][j].f!=1) wyn++; if (t[i-1][j-1].f==1&&t[i][j-2].f!=1) wyn++; if (t[i+1][j+1].f==1&&t[i+2][j].f!=1) wyn++; if (t[i+1][j+1].f==1&&t[i][j+2].f!=1) wyn++; if (t[i+1][j-1].f==1&&t[i+2][j].f!=1&&t[i+1][j+1].f!=1) wyn++; if (t[i+1][j-1].f==1&&t[i][j-2].f!=1&&t[i-1][j-1].f!=1) wyn++; if (t[i-1][j+1].f==1&&t[i-2][j].f!=1&&t[i-1][j-1].f!=1) wyn++; if (t[i-1][j+1].f==1&&t[i][j+2].f!=1&&t[i+1][j+1].f!=1) wyn++; wyn%=1000000007; } //printf ("%lld ", wyn); } } } printf ("%lld", wyn); } return 0; } |