zhcnyuyang 2016-09-25 07:00 采纳率: 0%
浏览 777

我在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条回答 默认 最新

  • threenewbee 2016-09-25 15:52
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决