題目連結: https://zerojudge.tw/ShowProblem?problemid=e287
# 解題思路
就依照題目的敘述做一遍吧！！
開一個陣列紀錄地圖，一個紀錄是否走過
有些比較難寫的部分要想辦法自己克服喔
(這題有 BFS 的影子)
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
bool vs[100][100]; | |
int a[100][100]; | |
int x[4]={ 0, 0, -1, 1 } , y[4]={ -1, 1, 0, 0 }; | |
long long sum=0; | |
int n,m, minY ,minX, tempX, tempY,newX,newY; | |
bool route(){ | |
int minn=1000000; | |
for(int i=0;i<4;i++){ | |
newX = minX+x[i] ,newY = minY+y[i]; | |
if((0 <= newX && newX <m && 0 <= newY && newY < n) && !vs[newY][newX] &&a[newY][newX] < minn) | |
minn=a[newY][newX], tempX=newX, tempY=newY; | |
} | |
if(minn==1000000) return false; | |
sum+=minn, minX=tempX, minY=tempY, vs[tempY][tempX]=true ; | |
return true; | |
} | |
int main(){ | |
cin>>n>>m; | |
int minn=1000000; | |
for(int i=0;i<n;i++){ | |
for(int j=0;j<m;j++){ | |
cin>>a[i][j]; | |
if(minn>a[i][j]) | |
minn=a[i][j], minY=i , minX=j; | |
} | |
} | |
sum+=minn, vs[minY][minX]=true; | |
while (route()); | |
cout<<sum; | |
} |
