记忆化搜索只有40分!求助必关注
查看原帖
记忆化搜索只有40分!求助必关注
1091535
hehe123313楼主2023/12/26 15:08
#include<iostream>
#include<cmath>
using namespace std;
const int N=110;
char a[N][N];
int n,m,T;
int r1,c1,r2,c2;
long long  dp[N][N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];
int dfs(int x,int y,int t)
{
    if(dp[x][y][t])
    return dp[x][y][t];
    if(abs(x-r2)+abs(y-c2)>t)
        return 0;
        if(t<0)
        return 0;
        if(x==r2&&y==c2&&t>=0)
            return 1;
        for(int i=0;i<4;i++)
        {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!st[nx][ny]&&a[nx][ny]=='.')
        {
            st[nx][ny]=true;
            dp[x][y][t]+=dfs(nx,ny,t-1);
            st[nx][ny]=false;
        }
    }
    return dp[x][y][t];
}
int main()
{
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    cin>>r1>>c1>>r2>>c2;
    if(a[r1][c1]=='*')
    {
        cout<<0;
        return 0;
    }
    st[r1][c1]=true;
    dfs(r1,c1,T);
    cout<<dp[r1][c1][T];
    
    
    
    return 0;
}
2023/12/26 15:08
加载中...