e287 - 機器人的路徑
題目描述
題目描述了一個機器人在一個矩陣地圖上移動的過程。機器人從地圖中數值最小的格子出發，每次移動到相鄰（上下左右）且未訪問過的數值最小的格子，直到沒有可移動的格子為止。目標是計算機器人路徑上所有格子的數值總和。
解題思路
這個問題可以使用貪婪演算法和深度優先搜尋 (DFS) 來解決。首先，找到地圖中數值最小的格子作為起點。然後，使用 DFS 遞迴地尋找相鄰的未訪問格子中數值最小的格子，並將其添加到路徑中。重複此過程，直到沒有未訪問的相鄰格子。在每次移動時，將訪問過的格子標記為已訪問，以避免重複訪問。最後，計算路徑上所有格子的數值總和。
複雜度分析
- 時間複雜度: O(m*n)，其中 m 和 n 是地圖的行數和列數。因為最壞的情況下，機器人可能需要訪問地圖中的每個格子一次。
- 空間複雜度: O(mn)，主要用於儲存地圖和遞迴呼叫堆疊。遞迴深度在最壞情況下可能達到 mn。
程式碼
#include <iostream>
using namespace std;
int ans=0,minn=1000000,mp[101][101],m,n,am,an;
void f(int x,int y){
ans+=mp[x][y];
mp[x][y]=-1;
int minnn=1000000;
if(x>0&&mp[x-1][y]!=-1){
minnn=min(mp[x-1][y],minnn);
}
if(y>0&&mp[x][y-1]!=-1){
minnn=min(mp[x][y-1],minnn);
}
if(x<m-1&&mp[x+1][y]!=-1){
minnn=min(mp[x+1][y],minnn);
}
if(y<n-1&&mp[x][y+1]!=-1){
minnn=min(mp[x][y+1],minnn);
}
if(x>0&&mp[x-1][y]==minnn){
f(x-1,y);
return;
}
if(y>0&&mp[x][y-1]==minnn){
f(x,y-1);
return;
}
if(x<m-1&&mp[x+1][y]==minnn){
f(x+1,y);
return;
}
if(y<n-1&&mp[x][y+1]==minnn){
f(x,y+1);
return;
}
}
int main(){
cin >> m >> n;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
cin >> mp[i][j];
if(minn>mp[i][j]){
minn=mp[i][j];
am=i;
an=j;
}
}
}
f(am,an);
cout << ans ;
}