求助!!!第三次和第四次都是TLE,这个递归方法有什么要改正的地方吗?
查看原帖
求助!!!第三次和第四次都是TLE,这个递归方法有什么要改正的地方吗?
532451
DEEP_lianchen楼主2021/6/29 22:19
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int findpaths(int **mark,int *p,int m,int n,int a,int b)
{

    if(m==a&&n==b)
    {
        *p=*p+1;
        return 0;
    }
    if(m+1<=a&&n<=b)
    {
        if(mark[m+1][n]==1)
        {
            findpaths(mark,p,m+1,n,a,b);
        }
    }
    if(m<=a&&n+1<=b)
    {
        if(mark[m][n+1]==1)
        {
            findpaths(mark,p,m,n+1,a,b);
        }
    }
    return 1;
}
int main(){
    int a,b,c,d,i,j,paths;
    paths=0;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    int **mark = (int**)malloc(sizeof(int *)*(a+1));
    for(i=0;i<=a;i++)
    {
        mark[i]=(int *)malloc(sizeof(int)*(b+1));
    }
    for(i=0;i<=a;i++)
    {
        for(j=0;j<=b;j++)
        {
            mark[i][j]=1;
        }
    }
    if(c<=a&&d<=b&&c>=0&&d>=0)
        mark[c][d]=0;
    if(c-2<=a&&d-1<=b&&c-2>=0&&d-1>=0)
        mark[c-2][d-1]=0;
    if(c-1<=a&&d-2<=b&&c-1>=0&&d-2>=0)
        mark[c-1][d-2]=0;
    if(c+1<=a&&d-2<=b&&c+1>=0&&d-2>=0)
        mark[c+1][d-2]=0;
    if(c+2<=a&&d-1<=b&&c+2>=0&&d-1>=0)
        mark[c+2][d-1]=0;
    if(c+2<=a&&d+1<=b&&c+2>=0&&d+1>=0)
        mark[c+2][d+1]=0;
    if(c+1<=a&&d+2<=b&&c+1>=0&&d+2>=0)
        mark[c+1][d+2]=0;
    if(c-1<=a&&d+2<=b&&c-1>=0&&d+2>=0)
        mark[c-1][d+2]=0;
    if(c-2<=a&&d+1<=b&&c-2>=0&&d+1>=0)
        mark[c-2][d+1]=0;
    i=0;
    j=0;
    findpaths(mark,&paths,i,j,a,b);
    printf("%d",paths);
    return 0;
}
2021/6/29 22:19
加载中...