游荡的奶牛题解

这一道题可以使用深搜，题目中并没有说不可以走回头路，且可以多次到达终点。我们只需要判断步数是否超过 $t$ ，超过则直接返回；当到达终点时，判断步数是否刚好等于 $t$ 。如果满足条件方案数加一，否则继续递归：

#include <bits/stdc++.h>
using namespace std;
char sz[105][105];
int n,m,t,r,c,R,C,ans=0,_x[]={0,1,0,-1},_y[]={1,0,-1,0};
bool check(int dx,int dy){
    return (dx>=1 and dx<=n and dy>=1 and dy<=m and sz[dx][dy]!='*');
}
void dfs(int x,int y,int flag){
    if(flag>t)return;
    if(x==R and y==C){
        if(flag==t){ 
            ans++;
        }
    }for(int i=0;i<4;i++){
        int dx=x+_x[i];
        int dy=y+_y[i];
        if(check(dx,dy)){
            dfs(dx,dy,flag+1);
        }
    }  
    
}
int main(){ 
    cin >> n >> m >> t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> sz[i][j];
        } 
    }cin >> r >> c >> R >> C;
    dfs(r,c,0);
    cout << ans;
    return 0;
}