题解 P3654 【First Step (ファーストステップ)】

rashoumon · 2020-03-15 10:59:31 · 题解

本题遍历每一个可以站人的点，然后利用dfs的思路判断每一个点向下和向右是否能满足条件；但是r=1时需要特判，因为r=1意味着向下和向右重复计算，需要除以2。

#include <iostream>
using namespace std;
int n,m,r,ans,dx[2]={0,1},dy[2]={1,0};//位移向量，分别是朝下和朝右
char map[105][105];
void skim(int x,int y,int i,int j)//dfs
{
    if(j>r){//满足条件则ans++
        ++ans;
        return ;
    }
    if(map[x][y]!='.'||x<0||y<0||x>=n||y>=m)//处理越界和障碍
        return ;
    skim(x+dx[i],y+dy[i],i,j+1);
    return ;
}
int main()
{
    cin>>n>>m>>r;
    for(int i=0;i<n;i++)
        cin>>map[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(map[i][j]=='.')
                for(int k=0;k<2;k++)
                    skim(i,j,k,1);
    if(r==1)
        ans/=2;//r=1时特判
    cout<<ans<<endl;
    return 0;
}