這題要上下左右四個方向檢視,應該會馬上想到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;
}