自动搬运

查看原文

来自洛谷，原作者为

	rashoumon 就算叶藏喝了酒，也是一个天使一般的好孩子啊

搬运于2025-08-24 21:51:16，当前版本为作者最后更新于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;
}