2 zhcnyuyang zhcnyuyang 于 2016.09.25 15:00 提问

我在poj上做3009题,超时了,求改进

如题,代码如下
#include
#include
using namespace std;
int w[100],h[100];
int arr[100][21][21];
int output[100];
int main(){

extern int dfs(int,int,int,int);
for(int i=1;i<=99;i++){
    output[i]=-1;
}
int i=0;
for(;;){
    int w0,h0;
    i++;
    scanf("%d %d",&w[i],&h[i]);
    if(w[i]==0&&h[i]==0){
        i=i-1;
        break;
    }
    for(int j=1;j<=h[i];j++){
        for(int k=1;k<=w[i];k++){
            scanf("%d",&arr[i][j][k]);
            if(arr[i][j][k]==2){
                w0=k;
                h0=j;
            }
        }
    }
    dfs(h0,w0,1,i);
}
for(int l=1;l<=i;l++){
    printf("%d\n",output[l]);
}
return 0;

}

void dfs(int x,int y,int step,int t){

if(step>10){
    return;
}
if(arr[t][x][y]==3){
    if(output[t]==-1){
        output[t]=step;
    }else if(output[t]!=0){
        if(step<output[t]){
            output[t]=step;
        }
    }
}//paichu
else{
    int a0[21][21];
    for(int i=1;i<=20;i++){
        for(int j=1;j<=20;j++){
            a0[i][j]=arr[t][i][j];
        }
    }
    //left
    if(y>1&&arr[t][x][y-1]!=1){
        int judge=0;
        int y1;
        for(int i=y;i>=1;i--){
            if(arr[t][x][i]==1){
                judge=1;
                y1=i+1;
                arr[t][x][i]=0;
                break;
            }
            if(arr[t][x][i]==3){
                judge=3;
                y1=i;
                break;
            }
        }
        if(judge==1){
            dfs(x,y1,step+1,t);
        }else if(judge==3){
            dfs(x,y1,step,t);
        }
        for(int i=1;i<=20;i++){
            for(int j=1;j<=20;j++){
                arr[t][i][j]=a0[i][j];
            }
        }
    }
    //right
    if(y<w[t]&&arr[t][x][y+1]!=1){
        int judge=0;
        int y1;
        for(int i=y;i<=w[t];i++){
            if(arr[t][x][i]==1){
                judge=1;
                y1=i-1;
                arr[t][x][i]=0;

                break;
            }
            if(arr[t][x][i]==3){
                judge=3;
                y1=i;

                break;
            }
        }
        if(judge==1){
            dfs(x,y1,step+1,t);
        }else if(judge==3){
            dfs(x,y1,step,t);
        }
        for(int i=1;i<=20;i++){
            for(int j=1;j<=20;j++){
                arr[t][i][j]=a0[i][j];
            }
        }
    }
    //up
    if(x>1&&arr[t][x-1][y]!=1){
        int judge=0;
        int x1;

        for(int i=x;i>=1;i--){
            if(arr[t][i][y]==1){
                judge=1;
                x1=i+1;
                arr[t][i][y]=0;

                break;
            }
            if(arr[t][i][y]==3){
                judge=3;
                x1=i;

                break;
            }
        }

        if(judge==1){
            dfs(x1,y,step+1,t);
        }else if(judge==3){
            dfs(x1,y,step,t);
        }
        for(int i=1;i<=20;i++){
            for(int j=1;j<=20;j++){
                arr[t][i][j]=a0[i][j];
            }
        }
    }
    //down
    if(x<h[t]&&arr[t][x+1][y]!=1){
        int judge=0;
        int x1;

        for(int i=x;i<=h[t];i++){
            if(arr[t][i][y]==1){
                judge=1;
                x1=i-1;
                arr[t][i][y]=0;

                break;
            }
            if(arr[t][i][y]==3){
                judge=3;
                x1=i;

                break;
            }
        }

        if(judge==1){
            dfs(x1,y,step+1,t);
        }else if(judge==3){
            dfs(x1,y,step,t);
        }
        for(int i=1;i<=20;i++){
            for(int j=1;j<=20;j++){
                arr[t][i][j]=a0[i][j];
            }
        }
    }
}

}
提交上去之后提示超时了,求各位帮我看看我的代码是什么问题,帮我改进一下,谢谢

1个回答

caozhy
caozhy   Ds   Rxr 2016.09.25 23:52
Csdn user default icon
上传中...
上传图片
插入图片