Loading... 题意:给出$n\times m$的矩阵,求有多少连续的$k$个`.`在同一行或同一列上 <!--more--> ## Problems 我们浦之星女子学院的篮球场是一个R行C列的矩阵,其中堆满了各种学校的杂物 (用"#"表示),空地 (用"."表示) 好像并不多的样子呢…… 我们Aqours现在已经一共有K个队员了,要歌唱舞蹈起来的话,我们得排成一条1*K的直线,一个接一个地站在篮球场的空地上呢 (横竖均可)。 我们想知道一共有多少种可行的站位方式呢。 Aqours的真正的粉丝的你,能帮我们算算吗? ## Input 第一行三个整数 R, C, K。 接下来的R行C列,是浦之星女子学院篮球场。 ## Output 总共的站位方式数量。 ## Samples ### Input ```txt 5 5 2 .###. ##.#. ..#.. #..#. #.### ``` ### Output ```txt 8 ``` ## Solve 从每个点开始深搜,固定方向,向下或向右 ## Code ```cpp #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ms(a,b) memset(a,b,sizeof(a)) const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; const int maxn=1e6+10; const int mod=1e9+7; const int maxm=1e3+10; using namespace std; char c[200][200]; int dir[2][2]={{0,1},{1,0}}; int ans=0; void dfs(int n,int m,int k,int cnt,int x,int y,int d) { if(cnt==k) { ans++; return; } int dx=x+dir[d][0]; int dy=y+dir[d][1]; if(dx>=0&&dy>=0&&dx<n&&dy<m&&c[dx][dy]=='.') dfs(n,m,k,cnt+1,dx,dy,d); } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); srand((unsigned int)time(NULL)); #endif ios::sync_with_stdio(false); cin.tie(0); int R,C,K; cin>>R>>C>>K; for(int i=0;i<R;i++) cin>>c[i]; for(int i=0;i<R;i++) { for(int j=0;j<C;j++) { if(c[i][j]=='.') { for(int k=0;k<2;k++) dfs(R,C,K,1,i,j,k); } } } cout<<ans/(1+(K==1))<<endl; #ifndef ONLINE_JUDGE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s.\n"; #endif return 0; } ``` Last modification:December 28, 2021 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏