题解 P1535 【游荡的奶牛】

· · 题解

为什么用暴搜+剪枝呢？这明显是一道动态规划题

状态转移方程

首先，我们定义dp[i][x][y]表示在第I秒时到（x,y）时的可能路线数

那么，显而易见 dp[0][start_x][start_y]=1

且我们可知，每一个点（x，y）可以由四个点（x+1,y）（x-1,y）（x,y+1）（x,y-1）到达

那么，根据加法原理，易得：

dp[i][x][y]=dp[i-1][x+1][y]+dp[I-1][x-1][y]+dp[I-1][x][y+1]+dp[I-1][x][y-1]

时间复杂度

O(tmn)

代码

#include<bits/stdc++.h>
using namespace std;
int dp[16][105][105];
int n,m,t;
bool a[105][105];
int start_x,start_y,end_x,end_y;
const int addmove[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main(){
    cin>>n>>m>>t;
    memset(a,true,sizeof(a));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char temp;
            cin>>temp;
            a[i][j]=!(temp=='*');
        }
    }
    cin>>start_x>>start_y>>end_x>>end_y;
    memset(dp,0,sizeof(dp));
    dp[0][start_x][start_y]=1;
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=m;k++)
                for(int p=0;p<4;p++){
                    if(!a[j][k])
                        dp[i][j][k]=0;
                    else
                        dp[i][j][k]+=dp[i-1][j+addmove[p][0]][k+addmove[p][1]];
                }
    cout<<dp[t][end_x][end_y];
}