題目說明#
有一個機器人會 n * m 圖中的最低點出發，找四個方向沒走過的最低點走並記錄數值。
解題過程#
這題比較直觀的解法是 dfs，首先先宣告需要用到的陣列
int a,b,minn= 1000000,minx,miny,ans = 0,arr[200][200]={},visited[200][200]={},dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
接著遍歷一次陣列找最小的數字，將值傳到函式，直到函式結束就輸出總和
int main(){
cin >> a >> b;
for(int i = 0; i < a; i++)
{
for(int j = 0; j < b; j++)
{
cin >> arr[i][j];
}
}
for(int i = 0; i < a; i++)
{
for(int j = 0; j < b; j++)
{
if(arr[i][j] < minn) minn = arr[i][j], minx = i, miny = j;
}
}
ans += minn;
dfs(arr, visited, minn, minx, miny);
cout << ans;
return 0;
}
如果該點已經訪問過了就回傳，沒有就找該點沒拜訪過最小的點並將該點的值累加，再呼叫函式，如果找不到了就回傳
void dfs(int arr[][200],int visited[][200],int dmin,int dx,int dy)
{
if(visited[dx][dy] == 1)return;
else
{
dmin = 1000000;
visited[dx][dy]=1;
int dminx = 0, dminy = 0,move = 0;
for(int k = 0; k < 4; k++)
{
int newx = dx + dir[k][0], newy = dy + dir[k][1];
if(newx >= 0 && newx < a && newy >= 0 && newy < b && visited[newx][newy] == 0 && arr[newx][newy] < dmin)
{
dmin = arr[newx][newy];
dminx = newx;
dminy = newy;
move = 1;
}
}
dx = dminx;
dy = dminy;
if(move)
{
ans += dmin;
dfs(arr, visited, dmin, dx, dy);
}
else return;
}
}
程式碼就完成了!
完整程式碼如下
#include <bits/stdc++.h>
using namespace std;
int a,b,minn= 1000000,minx,miny,ans = 0,arr[200][200]={},visited[200][200]={},dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
void dfs(int arr[][200],int visited[][200],int dmin,int dx,int dy)
{
if(visited[dx][dy] == 1)return;
else
{
dmin = 1000000;
visited[dx][dy]=1;
int dminx = 0, dminy = 0,move = 0;
for(int k = 0; k < 4; k++)
{
int newx = dx + dir[k][0], newy = dy + dir[k][1];
if(newx >= 0 && newx < a && newy >= 0 && newy < b && visited[newx][newy] == 0 && arr[newx][newy] < dmin)
{
dmin = arr[newx][newy];
dminx = newx;
dminy = newy;
move = 1;
}
}
dx = dminx;
dy = dminy;
if(move)
{
ans += dmin;
dfs(arr, visited, dmin, dx, dy);
}
else return;
}
}
int main(){
cin >> a >> b;
for(int i = 0; i < a; i++)
{
for(int j = 0; j < b; j++)
{
cin >> arr[i][j];
}
}
for(int i = 0; i < a; i++)
{
for(int j = 0; j < b; j++)
{
if(arr[i][j] < minn) minn = arr[i][j], minx = i, miny = j;
}
}
ans += minn;
dfs(arr, visited, minn, minx, miny);
cout << ans;
return 0;
}
