CCPC-Wannafly Winter Camp Day1 (Div2, onsite) B 吃豆豆 DP

B-吃豆豆

思路：3维DP维护一个3维数组，表示(i,j)位置第K秒有多少糖果，通过k-1秒5个位置转移得到(i,j,k)

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10010;
int dp[20][20][maxn];
int mp[20][20];
int main(){
    int n,m,c,xs,ys,xt,yt;
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&mp[i][j]);
    scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
    memset(dp,-0x3f,sizeof(dp));
    dp[xs][ys][0]=0;
    for(int k=1;k<maxn;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        dp[i][j][k]=max({dp[i-1][j][k-1],dp[i][j+1][k-1],dp[i+1][j][k-1],dp[i][j-1][k-1],dp[i][j][k-1]})+(k%mp[i][j]==0?1:0);
    }
    int _max=-1;
    for(int i=0;i<maxn;i++)if(dp[xt][yt][i]>=c){_max=i;break;}
    printf("%d\n",_max);
}