#include<bits/stdc++.h> using namespace std; //#define mod 10000000009; bool tab[3010][3010]; pair<int, int> kier[] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; struct moj { pair<short int, short int> x[4]; moj() { for( int i=0; i<4; i++ ) { x[i] = {0, 0}; } } bool operator < ( const moj & other ) const { for( int i=0; i<4; i++ ) { if( x[i] != other.x[i] ) return x[i] < other.x[i]; } return 0; } }; moj pom; vector<moj> wy; int n; void algo( int k ) { bool czy; for( int i=1; i<=n; i++ ) { for( int j=1; j<=n; j++ ) { if( tab[i][j] == 0 ) { czy = 0; for( auto & a : kier ) { if( tab[i+a.first][j+a.second] ) { czy = 1; break; } } if( !czy ) continue; pom.x[k] = {i, j}; if( k ) { tab[i][j] = 1; algo( k-1 ); tab[i][j] = 0; } else { wy.push_back( pom ); } } } } } int32_t main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); int k; cin >> n >> k; k--; for( int i=1; i<=n; i++ ) { char a; for( int j=1; j<=n; j++ ) { cin >> a; if( a=='#' ) tab[i][j] = 1; } } algo( k ); for( auto & i : wy ) { sort( i.x, i.x+4 ); } sort( wy.begin(), wy.end() ); int res = 1; for( int i=1; i<wy.size(); i++ ) { /*for( int j=0; j<4; j++ ) { cout << wy[i].x[j].first << " " << wy[i].x[j].second << " "; } cout << "\n";*/ if( wy[i] < wy[i-1] || wy[i-1] < wy[i] ) res++; } cout << res; 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<bits/stdc++.h> using namespace std; //#define mod 10000000009; bool tab[3010][3010]; pair<int, int> kier[] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; struct moj { pair<short int, short int> x[4]; moj() { for( int i=0; i<4; i++ ) { x[i] = {0, 0}; } } bool operator < ( const moj & other ) const { for( int i=0; i<4; i++ ) { if( x[i] != other.x[i] ) return x[i] < other.x[i]; } return 0; } }; moj pom; vector<moj> wy; int n; void algo( int k ) { bool czy; for( int i=1; i<=n; i++ ) { for( int j=1; j<=n; j++ ) { if( tab[i][j] == 0 ) { czy = 0; for( auto & a : kier ) { if( tab[i+a.first][j+a.second] ) { czy = 1; break; } } if( !czy ) continue; pom.x[k] = {i, j}; if( k ) { tab[i][j] = 1; algo( k-1 ); tab[i][j] = 0; } else { wy.push_back( pom ); } } } } } int32_t main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); int k; cin >> n >> k; k--; for( int i=1; i<=n; i++ ) { char a; for( int j=1; j<=n; j++ ) { cin >> a; if( a=='#' ) tab[i][j] = 1; } } algo( k ); for( auto & i : wy ) { sort( i.x, i.x+4 ); } sort( wy.begin(), wy.end() ); int res = 1; for( int i=1; i<wy.size(); i++ ) { /*for( int j=0; j<4; j++ ) { cout << wy[i].x[j].first << " " << wy[i].x[j].second << " "; } cout << "\n";*/ if( wy[i] < wy[i-1] || wy[i-1] < wy[i] ) res++; } cout << res; return 0; } |