bobobo0413
(杜拜、慕尼黑、蘇黎世、清邁、東京、首爾、布拉格)
學校
:
國立臺灣大學
編號 : 252359
來源 : [118.169.16.153]
最後登入時間 ：
2024-05-05 22:46:10
這題要上下左右四個方向檢視，應該會馬上想到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;
}
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [210.71.71.103]
最後登入時間 ：
2024-05-06 12:16:25
我覺得這題不太算 bfs，決定下一步要往哪裡走以後，就不會需要回到這一步再做別的動作了。
可以把 bfs 的寫法拿掉，改成一個迴圈即可，這樣會減少一些遞迴占用的堆疊空間。
#include<cstdio>
int ans=0;
int a[100][100],m,n;
bool v[100][100]={false};
#define f 1e6
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;
}
}
while(1) {
int &b=y, &c=x; // bfs(y, x);
static 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) break; // 將return改成break 離開迴圈
// bfs(d,e);
y = d;
x = e;
}
printf("%d\n",ans);
return 0;
}
不過這支程式無法 2ms 應該是因為 io 問題，我自己 AC(2ms, 112KB) 的程式碼套用 cstdio 也是3ms
bobobo0413
(杜拜、慕尼黑、蘇黎世、清邁、東京、首爾、布拉格)
學校
:
國立臺灣大學
編號 : 252359
來源 : [118.169.16.153]
最後登入時間 ：
2024-05-05 22:46:10
我覺得這題不太算 bfs，決定下一步要往哪裡走以後，就不會需要回到這一步再做別的動作了。
可以把 bfs 的寫法拿掉，改成一個迴圈即可，這樣會減少一些遞迴占用的堆疊空間。#include int ans=0; int a[100][100],m,n; bool v[100][100]={false}; #define f 1e6 int main() { scanf("%d%d",&m,&n); int i,j,s=f,x,y; for(i=0;ia[i][j]) { s=a[i][j]; x=j; y=i; } } while(1) { int &b=y, &c=x; // bfs(y, x); static int t=f,d,e,k; ans+=a[b][c]; v[b][c]=true; if(b+1a[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+1a[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) break; // 將return改成break 離開迴圈 // bfs(d,e); y = d; x = e; } printf("%d\n",ans); return 0;
}不過這支程式無法 2ms 應該是因為 io 問題，我自己 AC(2ms, 112KB) 的程式碼套用 cstdio 也是3ms
因為講義把這題放BFS和DFS的那章，好像第七章的樣子，不過用迴圈好像比較好耶!
bobobo0413
(杜拜、慕尼黑、蘇黎世、清邁、東京、首爾、布拉格)
學校
:
國立臺灣大學
編號 : 252359
來源 : [118.169.16.153]
最後登入時間 ：
2024-05-05 22:46:10
我覺得這題不太算 bfs，決定下一步要往哪裡走以後，就不會需要回到這一步再做別的動作了。
可以把 bfs 的寫法拿掉，改成一個迴圈即可，這樣會減少一些遞迴占用的堆疊空間。#include int ans=0; int a[100][100],m,n; bool v[100][100]={false}; #define f 1e6 int main() { scanf("%d%d",&m,&n); int i,j,s=f,x,y; for(i=0;ia[i][j]) { s=a[i][j]; x=j; y=i; } } while(1) { int &b=y, &c=x; // bfs(y, x); static int t=f,d,e,k; ans+=a[b][c]; v[b][c]=true; if(b+1a[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+1a[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) break; // 將return改成break 離開迴圈 // bfs(d,e); y = d; x = e; } printf("%d\n",ans); return 0;
}不過這支程式無法 2ms 應該是因為 io 問題，我自己 AC(2ms, 112KB) 的程式碼套用 cstdio 也是3ms
我剛剛測試，超時耶，看起來不行
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [210.71.71.103]
最後登入時間 ：
2024-05-06 12:16:25
我剛剛測試，超時耶，看起來不行
不好意思，程式碼沒複製好。
#include<cstdio>int ans=0;int a[100][100],m,n;bool v[100][100]={false};#define f 1e6int 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; } } while(1) { int &b=y, &c=x; // bfs(y, x); 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) break; // 將return改成break 離開迴圈 // bfs(d,e); y = d; x = e; } printf("%d\n",ans); return 0;
}