#include <bits/stdc++.h> using namespace std; #define ff first #define dd second #define mp make_pair #define lld long long #define sz size() #define pb push_back #define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i) #define gecx() getchar() #define pii pair<int,int> #define piii pair<pair<pii ,pii >,pair<pii ,pii > > template<typename T> void scan(T &i) { T tt; char cc; tt=0; cc='a'; bool neg=0; while(cc>'9' || cc<'0') { if(cc=='-') neg=1; cc=gecx(); } while(cc>='0' && cc<='9') { tt=(tt<<3ll)+(tt<<1ll)+cc-'0'; cc=gecx(); } *i=tt; } bitset<3001>odw[3001]; char s[3001]; map<set<pii>,int>c; lld wyn; int x,y; /* void dfs(int a, int b, set<pii> xd, int k) { if(a>x || b>y)return; cout<<a<<" "<<b<<" "<<k<<endl; if(!k){++wyn;return;} c[xd]=1; odw[a][b]=1; xd.insert(mp(a+1,b)); if(!c[xd] && x>a+1 && !odw[a+1][b]) dfs(a+1,b,xd,k-1); xd.insert(mp(a-1,b)); if(!c[xd] && a && !odw[a-1][b]) dfs(a-1,b,xd,k-1); xd.insert(=mp(a,b+1)); if(!c[xd] && b<y-1 && !odw[a][b+1]) dfs(a,b+1,xd,k-1); xd.insert(mp(a,b-1)); if(!c[xd] && b && !odw[a][b-1]) dfs(a,b-1,xd,k-1); odw[a][b]=0; } */ bool chk(int a, int b) { if(a && odw[a-1][b])return 1; else if(a<x-1 && odw[a+1][b])return 1; else if(b && odw[a][b-1])return 1; else if(b<x-1 && odw[a][b+1])return 1; else return 0; } void bfs(set<pii> xd,int k) { // cout<<k<<endl; if(!k){++wyn;return;} For(i,0,x) For(j,0,x) { // cout<<i<<" "<<j<<" "<<k<<endl; if(!odw[i][j] && chk(i,j)) { odw[i][j]=1; xd.insert(mp(i,j)); if(!c[xd]){ c[xd]=1; bfs(xd,k-1);} odw[i][j]=0; xd.erase(xd.find(mp(i,j))); } } } int main() { scanf("%d%d", &x,&y); For(i,0,x) { scanf("%s",s); For(j,0,x) if(s[j]=='#') odw[i][j]=1; } set<pii> xd; xd.insert(mp(-1,-1)); bfs(xd,y); printf("%lld",wyn); }
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 | #include <bits/stdc++.h> using namespace std; #define ff first #define dd second #define mp make_pair #define lld long long #define sz size() #define pb push_back #define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i) #define gecx() getchar() #define pii pair<int,int> #define piii pair<pair<pii ,pii >,pair<pii ,pii > > template<typename T> void scan(T &i) { T tt; char cc; tt=0; cc='a'; bool neg=0; while(cc>'9' || cc<'0') { if(cc=='-') neg=1; cc=gecx(); } while(cc>='0' && cc<='9') { tt=(tt<<3ll)+(tt<<1ll)+cc-'0'; cc=gecx(); } *i=tt; } bitset<3001>odw[3001]; char s[3001]; map<set<pii>,int>c; lld wyn; int x,y; /* void dfs(int a, int b, set<pii> xd, int k) { if(a>x || b>y)return; cout<<a<<" "<<b<<" "<<k<<endl; if(!k){++wyn;return;} c[xd]=1; odw[a][b]=1; xd.insert(mp(a+1,b)); if(!c[xd] && x>a+1 && !odw[a+1][b]) dfs(a+1,b,xd,k-1); xd.insert(mp(a-1,b)); if(!c[xd] && a && !odw[a-1][b]) dfs(a-1,b,xd,k-1); xd.insert(=mp(a,b+1)); if(!c[xd] && b<y-1 && !odw[a][b+1]) dfs(a,b+1,xd,k-1); xd.insert(mp(a,b-1)); if(!c[xd] && b && !odw[a][b-1]) dfs(a,b-1,xd,k-1); odw[a][b]=0; } */ bool chk(int a, int b) { if(a && odw[a-1][b])return 1; else if(a<x-1 && odw[a+1][b])return 1; else if(b && odw[a][b-1])return 1; else if(b<x-1 && odw[a][b+1])return 1; else return 0; } void bfs(set<pii> xd,int k) { // cout<<k<<endl; if(!k){++wyn;return;} For(i,0,x) For(j,0,x) { // cout<<i<<" "<<j<<" "<<k<<endl; if(!odw[i][j] && chk(i,j)) { odw[i][j]=1; xd.insert(mp(i,j)); if(!c[xd]){ c[xd]=1; bfs(xd,k-1);} odw[i][j]=0; xd.erase(xd.find(mp(i,j))); } } } int main() { scanf("%d%d", &x,&y); For(i,0,x) { scanf("%s",s); For(j,0,x) if(s[j]=='#') odw[i][j]=1; } set<pii> xd; xd.insert(mp(-1,-1)); bfs(xd,y); printf("%lld",wyn); } |