有意點點類似 BFS ，不過一次只會有一個分支，以下是程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<iostream>
#include<deque>
#define MAX 1000000
using namespace std;
struct step{
long long x,y;
};
int main(){
int n,m,min=MAX+1;
cin>>n>>m;
long long sum=0;
step best;
int mp[110][110]={MAX};
for(int i=0;i<110;i++){
for(int j=0;j<110;j++){
mp[i][j]=MAX;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(min>mp[i][j]){
min=mp[i][j];
best.x=j;best.y=i;sum=min;
}
}
}
deque<step> st;
st.push_front(best);
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
while(!st.empty()){
step now=st.back();
st.pop_back();
min=MAX;
mp[now.y][now.x]=MAX;
for(int i=0;i<4;i++){
step next;
next.x=now.x+dx[i];
next.y=now.y+dy[i];
if(mp[next.y][next.x]<min){
min=mp[next.y][next.x];
best.x=next.x;best.y=next.y;
}
}
if(min==MAX){
continue;
}else{
sum+=mp[best.y][best.x];
st.push_front(best);
}
}
cout<<sum;
return 0;
}
|