#38861: c++(3ms,124kb)嘗試很久優化,感覺極限了,2ms或3ms小於124kb的高手,不知道怎麼寫的


bobobo0413 (杜拜、慕尼黑、蘇黎世、清邁、東京、首爾、布拉格)

學校 : 國立臺灣大學
編號 : 252359
來源 : [118.169.16.153]
最後登入時間 :
2024-05-05 22:46:10
e287. 機器人的路徑 -- APCS | From: [114.137.135.166] | 發表日期 : 2023-12-28 14:48

這題要上下左右四個方向檢視,應該會馬上想到BFS,因為講義有說BFS功能是優先遍歷鄰居,為了讓陣列可在遞迴用到,我直接設在全域。輸入陣列時,要順便找最小值以及其座標,然後呼叫BFS。首先要記錄走過陣列的分數和設定為已走過。然後上下左右尋找邊界內,沒走過,以及最小值,我合併一起寫讓程式乾淨。最後上下左右不能移動給他停止,輸出累積的分數。以下提供C++原始碼,C和JAVA我還要再研究:

#include<cstdio>
int ans=0;
int a[100][100],m,n;
bool v[100][100]={false};
#define f 1e6
void bfs(int b,int c)
{
            int t=f,d,e,k;
    ans+=a[b][c];
v[b][c]=true;
if(b+1<m&&v[b+1][c]==false&&t>a[b+1][c])
{
    t=a[b+1][c];
    d=b+1;
    e=c;
}
if(b-1>=0&&v[b-1][c]==false&&t>a[b-1][c])
{
    t=a[b-1][c];
    d=b-1;
    e=c;
}
if(c+1<n&&v[b][c+1]==false&&t>a[b][c+1])
{
    t=a[b][c+1];
    d=b;
    e=c+1;
}
if(c-1>=0&&v[b][c-1]==false&&t>a[b][c-1])
{
    t=a[b][c-1];
    d=b;
    e=c-1;
}
if(t==f)
    return ;
         bfs(d,e);
}
int main()
{
        scanf("%d%d",&m,&n);
    int i,j,s=f,x,y;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
    {
        scanf("%d",&a[i][j]);
if(s>a[i][j])
{
    s=a[i][j];
    x=j;
    y=i;
}
    }
bfs(y,x);
printf("%d\n",ans);
return 0;
}

 
ZeroJudge Forum