#include <iostream> #include <vector> using namespace std; typedef long long LL; const LL MOD = 1000000007; int tab[3009][3009]; int is[3009][3009]; vector< pair<int, int> >vec; LL res; int n, k; void k1() { res = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(tab[i][j] == 0 && (tab[i][j + 1] || tab[i][j - 1] || tab[i + 1][j] || tab[i - 1][j])) ++res; } void k2() { LL cnt = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { if(tab[i][j] == 0 && (tab[i][j + 1] || tab[i][j - 1] || tab[i + 1][j] || tab[i - 1][j])) { is[i][j] = 0; ++cnt; vec.push_back(make_pair(i, j)); } else if(tab[i][j] == 0)is[i][j] = 1; } --cnt; res = 0; for(int a = 0; a < vec.size(); ++a) { res += cnt; int i = vec[a].first; int j = vec[a].second; if(is[i][j + 1] || is[i][j - 1] || is[i + 1][j] || is[i - 1][j]) ++res; --cnt; } } void k3() { res = 243562456245; } void k4() { res = 2534536673467; } int main() { ios_base :: sync_with_stdio(0); string s; int i, j; cin >> n >> k; for(i = 0; i <= n + 1; ++i) is[0][i] = tab[0][i] = 0; for(i = 0; i <= n + 1; ++i) is[n + 1][i] = tab[n + 1][i] = 0; for(i = 0; i <= n + 1; ++i) is[i][0] = tab[i][0] = 0; for(i = 0; i <= n + 1; ++i) is[i][n + 1] = tab[i][n + 1] = 0; for(i = 0; i <= n; ++i) { getline(cin, s); for(j = 1; j <= s.length(); ++j) tab[i][j] = (s[j - 1] == '#') ? 1 : 0; } if(k == 1) k1(); else if(k == 2) k2(); else if(k == 3) k3(); else k4(); cout << res % MOD << endl; 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 | #include <iostream> #include <vector> using namespace std; typedef long long LL; const LL MOD = 1000000007; int tab[3009][3009]; int is[3009][3009]; vector< pair<int, int> >vec; LL res; int n, k; void k1() { res = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(tab[i][j] == 0 && (tab[i][j + 1] || tab[i][j - 1] || tab[i + 1][j] || tab[i - 1][j])) ++res; } void k2() { LL cnt = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { if(tab[i][j] == 0 && (tab[i][j + 1] || tab[i][j - 1] || tab[i + 1][j] || tab[i - 1][j])) { is[i][j] = 0; ++cnt; vec.push_back(make_pair(i, j)); } else if(tab[i][j] == 0)is[i][j] = 1; } --cnt; res = 0; for(int a = 0; a < vec.size(); ++a) { res += cnt; int i = vec[a].first; int j = vec[a].second; if(is[i][j + 1] || is[i][j - 1] || is[i + 1][j] || is[i - 1][j]) ++res; --cnt; } } void k3() { res = 243562456245; } void k4() { res = 2534536673467; } int main() { ios_base :: sync_with_stdio(0); string s; int i, j; cin >> n >> k; for(i = 0; i <= n + 1; ++i) is[0][i] = tab[0][i] = 0; for(i = 0; i <= n + 1; ++i) is[n + 1][i] = tab[n + 1][i] = 0; for(i = 0; i <= n + 1; ++i) is[i][0] = tab[i][0] = 0; for(i = 0; i <= n + 1; ++i) is[i][n + 1] = tab[i][n + 1] = 0; for(i = 0; i <= n; ++i) { getline(cin, s); for(j = 1; j <= s.length(); ++j) tab[i][j] = (s[j - 1] == '#') ? 1 : 0; } if(k == 1) k1(); else if(k == 2) k2(); else if(k == 3) k3(); else k4(); cout << res % MOD << endl; return 0; } |