#include <stdio.h> int n, k, i=0, j=0, F[9000001], iF=0, jF=0, c, a, b, lab[3001][3001], fun=0, dup[3001][3001]; char ar[3001][3001], z; bool check[3001][3001]; long long wynn=0, d, dd, ddd, dddd, mm, M=1000000007; int main(){ scanf ("%d %d", &n, &k); while (i<n){ z=getchar(); while (j<n){ ar[i][j]=getchar(); if (ar[i][j]=='#') check[i][j]=1, F[jF]=i*3001+j, jF++; else lab[i][j]=10001; j++; } j=0, i++; } c=jF; while (iF<c){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&check[a][b+1]==0) check[a][b+1]=1, lab[a][b+1]=1, F[jF]=a*3001+b+1, jF++; if (b>0&&check[a][b-1]==0) check[a][b-1]=1, lab[a][b-1]=1, F[jF]=a*3001+b-1, jF++; if (a<n-1&&check[a+1][b]==0) check[a+1][b]=1, lab[a+1][b]=1, F[jF]=(a+1)*3001+b, jF++; if (a>0&&check[a-1][b]==0) check[a-1][b]=1, lab[a-1][b]=1, F[jF]=(a-1)*3001+b, jF++; iF++; } if (k==1) printf ("%d", jF-c); if (k==2){ d=jF-c; wynn=(wynn+(d*(d-1))/2)%M; while (iF<jF){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&lab[a][b+1]==10001) mm++; if (b>0&&lab[a][b-1]==10001) mm++; if (a<n-1&&lab[a+1][b]==10001) mm++; if (a>0&&lab[a-1][b]==10001) mm++; iF++; } wynn=(wynn+mm)%M; printf ("%lld", wynn); } if (k==3){ d=jF-c; dd=d-1; ddd=d-2; if (d%2==0) d/=2; else dd/=2; if (d%3==0) d/=3; else if (dd%3==0) dd/=3; else ddd/=3; wynn=wynn+(((d*dd)%M)*ddd)%M; // printf ("%lld\n", wynn); d=jF-c; c=jF; while (iF<c){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&lab[a][b+1]==10001) { dup[a][b+1]++; if (check[a][b+1]==0) check[a][b+1]=1, F[jF]=3001*a+b+1, jF++; fun++; if (b<n-2&&lab[a][b+2]==10001) mm++; if (a>0&&lab[a-1][b+1]==10001) mm++; if (a<n-1&&lab[a+1][b+1]==10001) mm++; } if (b>0&&lab[a][b-1]==10001){ dup[a][b-1]++; if (check[a][b-1]==0) check[a][b-1]=1, F[jF]=3001*a+b-1, jF++; fun++; if (b-2>0&&lab[a][b-2]==10001) mm++; if (a>0&&lab[a-1][b-1]==10001) mm++; if (a<n-1&&lab[a+1][b-1]==10001) mm++; } if (a<n-1&&lab[a+1][b]==10001){ dup[a+1][b]++; if (check[a+1][b]==0) check[a+1][b]=1, F[jF]=3001*(a+1)+b, jF++; fun++; if (a<n-2&&lab[a+2][b]==10001) mm++; if (b>0&&lab[a+1][b-1]==10001) mm++; if (b<n-1&&lab[a+1][b+1]==10001) mm++; } if (a>0&&lab[a-1][b]==10001){ dup[a-1][b]++; if (check[a-1][b]==0) check[a-1][b]=1, F[jF]=3001*(a-1)+b, jF++; fun++; if (a>1&&lab[a-2][b]==10001) mm++; if (b>0&&lab[a-1][b-1]==10001) mm++; if (b<n-1&&lab[a-1][b+1]==10001) mm++; } wynn=(wynn+(fun*(fun-1))/2)%M; fun=0, iF++; } wynn=(wynn+mm)%M; mm=0; // printf ("%lld\n", wynn); while (c<jF){ a=F[c]/3001, b=F[c]%3001; wynn=wynn+((d-dup[a][b])%M)*dup[a][b]+(dup[a][b]*(dup[a][b]-1))/2; wynn=wynn%M; c++; } printf ("%lld", wynn); } /* if (k==4){ d=jF-c; dd=d-1; ddd=d-2; dddd=d-3; if (d%2==0) d/=2; else dd/=2; if (d%3==0) d/=3; else if (dd%3==0) dd/=3; else ddd/=3; if (d%4==0) d/=4; else if (dd%4==0) dd/=4; else if (ddd%4==0) ddd/=4; else dddd/=4; wynn=wynn+(((((d*dd)%M)*ddd)%M)*dddd)%M; d=jF-c; c=jF; while (iF<c){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&lab[a][b+1]==10001) { dup[a][b+1]++; if (check[a][b+1]==0) check[a][b+1]=1, F[jF]=3001*a+b+1, jF++; fun++; if (b<n-2&&lab[a][b+2]==10001) mm++; if (a>0&&lab[a-1][b+1]==10001) mm++; if (a<n-1&&lab[a+1][b+1]==10001) mm++; } if (b>0&&lab[a][b-1]==10001){ dup[a][b-1]++; if (check[a][b-1]==0) check[a][b-1]=1, F[jF]=3001*a+b-1, jF++; fun++; if (b-2>0&&lab[a][b-2]==10001) mm++; if (a>0&&lab[a-1][b-1]==10001) mm++; if (a<n-1&&lab[a+1][b-1]==10001) mm++; } if (a<n-1&&lab[a+1][b]==10001){ dup[a+1][b]++; if (check[a+1][b]==0) check[a+1][b]=1, F[jF]=3001*(a+1)+b, jF++; fun++; if (a<n-2&&lab[a+2][b]==10001) mm++; if (b>0&&lab[a+1][b-1]==10001) mm++; if (b<n-1&&lab[a+1][b+1]==10001) mm++; } if (a>0&&lab[a-1][b]==10001){ dup[a-1][b]++; if (check[a-1][b]==0) check[a-1][b]=1, F[jF]=3001*(a-1)+b, jF++; fun++; if (a>1&&lab[a-2][b]==10001) mm++; if (b>0&&lab[a-1][b-1]==10001) mm++; if (b<n-1&&lab[a-1][b+1]==10001) mm++; } wynn=(wynn+(fun*(fun-1))/2)%M; fun=0, iF++; } while (c<jF){ a=F[c]/3001, b=F[c]%3001; wynn=wynn+((d-dup[a][b])%M)*dup[a][b]+(dup[a][b]*(dup[a][b]-1))/2; wynn=wynn%M; c++; } }*/ 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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 | #include <stdio.h> int n, k, i=0, j=0, F[9000001], iF=0, jF=0, c, a, b, lab[3001][3001], fun=0, dup[3001][3001]; char ar[3001][3001], z; bool check[3001][3001]; long long wynn=0, d, dd, ddd, dddd, mm, M=1000000007; int main(){ scanf ("%d %d", &n, &k); while (i<n){ z=getchar(); while (j<n){ ar[i][j]=getchar(); if (ar[i][j]=='#') check[i][j]=1, F[jF]=i*3001+j, jF++; else lab[i][j]=10001; j++; } j=0, i++; } c=jF; while (iF<c){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&check[a][b+1]==0) check[a][b+1]=1, lab[a][b+1]=1, F[jF]=a*3001+b+1, jF++; if (b>0&&check[a][b-1]==0) check[a][b-1]=1, lab[a][b-1]=1, F[jF]=a*3001+b-1, jF++; if (a<n-1&&check[a+1][b]==0) check[a+1][b]=1, lab[a+1][b]=1, F[jF]=(a+1)*3001+b, jF++; if (a>0&&check[a-1][b]==0) check[a-1][b]=1, lab[a-1][b]=1, F[jF]=(a-1)*3001+b, jF++; iF++; } if (k==1) printf ("%d", jF-c); if (k==2){ d=jF-c; wynn=(wynn+(d*(d-1))/2)%M; while (iF<jF){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&lab[a][b+1]==10001) mm++; if (b>0&&lab[a][b-1]==10001) mm++; if (a<n-1&&lab[a+1][b]==10001) mm++; if (a>0&&lab[a-1][b]==10001) mm++; iF++; } wynn=(wynn+mm)%M; printf ("%lld", wynn); } if (k==3){ d=jF-c; dd=d-1; ddd=d-2; if (d%2==0) d/=2; else dd/=2; if (d%3==0) d/=3; else if (dd%3==0) dd/=3; else ddd/=3; wynn=wynn+(((d*dd)%M)*ddd)%M; // printf ("%lld\n", wynn); d=jF-c; c=jF; while (iF<c){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&lab[a][b+1]==10001) { dup[a][b+1]++; if (check[a][b+1]==0) check[a][b+1]=1, F[jF]=3001*a+b+1, jF++; fun++; if (b<n-2&&lab[a][b+2]==10001) mm++; if (a>0&&lab[a-1][b+1]==10001) mm++; if (a<n-1&&lab[a+1][b+1]==10001) mm++; } if (b>0&&lab[a][b-1]==10001){ dup[a][b-1]++; if (check[a][b-1]==0) check[a][b-1]=1, F[jF]=3001*a+b-1, jF++; fun++; if (b-2>0&&lab[a][b-2]==10001) mm++; if (a>0&&lab[a-1][b-1]==10001) mm++; if (a<n-1&&lab[a+1][b-1]==10001) mm++; } if (a<n-1&&lab[a+1][b]==10001){ dup[a+1][b]++; if (check[a+1][b]==0) check[a+1][b]=1, F[jF]=3001*(a+1)+b, jF++; fun++; if (a<n-2&&lab[a+2][b]==10001) mm++; if (b>0&&lab[a+1][b-1]==10001) mm++; if (b<n-1&&lab[a+1][b+1]==10001) mm++; } if (a>0&&lab[a-1][b]==10001){ dup[a-1][b]++; if (check[a-1][b]==0) check[a-1][b]=1, F[jF]=3001*(a-1)+b, jF++; fun++; if (a>1&&lab[a-2][b]==10001) mm++; if (b>0&&lab[a-1][b-1]==10001) mm++; if (b<n-1&&lab[a-1][b+1]==10001) mm++; } wynn=(wynn+(fun*(fun-1))/2)%M; fun=0, iF++; } wynn=(wynn+mm)%M; mm=0; // printf ("%lld\n", wynn); while (c<jF){ a=F[c]/3001, b=F[c]%3001; wynn=wynn+((d-dup[a][b])%M)*dup[a][b]+(dup[a][b]*(dup[a][b]-1))/2; wynn=wynn%M; c++; } printf ("%lld", wynn); } /* if (k==4){ d=jF-c; dd=d-1; ddd=d-2; dddd=d-3; if (d%2==0) d/=2; else dd/=2; if (d%3==0) d/=3; else if (dd%3==0) dd/=3; else ddd/=3; if (d%4==0) d/=4; else if (dd%4==0) dd/=4; else if (ddd%4==0) ddd/=4; else dddd/=4; wynn=wynn+(((((d*dd)%M)*ddd)%M)*dddd)%M; d=jF-c; c=jF; while (iF<c){ a=F[iF]/3001, b=F[iF]%3001; if (b<n-1&&lab[a][b+1]==10001) { dup[a][b+1]++; if (check[a][b+1]==0) check[a][b+1]=1, F[jF]=3001*a+b+1, jF++; fun++; if (b<n-2&&lab[a][b+2]==10001) mm++; if (a>0&&lab[a-1][b+1]==10001) mm++; if (a<n-1&&lab[a+1][b+1]==10001) mm++; } if (b>0&&lab[a][b-1]==10001){ dup[a][b-1]++; if (check[a][b-1]==0) check[a][b-1]=1, F[jF]=3001*a+b-1, jF++; fun++; if (b-2>0&&lab[a][b-2]==10001) mm++; if (a>0&&lab[a-1][b-1]==10001) mm++; if (a<n-1&&lab[a+1][b-1]==10001) mm++; } if (a<n-1&&lab[a+1][b]==10001){ dup[a+1][b]++; if (check[a+1][b]==0) check[a+1][b]=1, F[jF]=3001*(a+1)+b, jF++; fun++; if (a<n-2&&lab[a+2][b]==10001) mm++; if (b>0&&lab[a+1][b-1]==10001) mm++; if (b<n-1&&lab[a+1][b+1]==10001) mm++; } if (a>0&&lab[a-1][b]==10001){ dup[a-1][b]++; if (check[a-1][b]==0) check[a-1][b]=1, F[jF]=3001*(a-1)+b, jF++; fun++; if (a>1&&lab[a-2][b]==10001) mm++; if (b>0&&lab[a-1][b-1]==10001) mm++; if (b<n-1&&lab[a-1][b+1]==10001) mm++; } wynn=(wynn+(fun*(fun-1))/2)%M; fun=0, iF++; } while (c<jF){ a=F[c]/3001, b=F[c]%3001; wynn=wynn+((d-dup[a][b])%M)*dup[a][b]+(dup[a][b]*(dup[a][b]-1))/2; wynn=wynn%M; c++; } }*/ return 0;} |