2023.1.25 PM 02:40 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=e287 出題者 : 2019年6月APCS 標籤 : DFS(深度優先搜尋) 難易度 : 2
解題想法 : 依照題目要求實作,對於現在的點,找到四周最小值,假如有找到,就繼續下去,反之就回傳目前累積的總和。 此題是較古老的APCS考古題,故難度較簡單,因此也是初學者們可以挑戰看看的題目。
//C++ language
#include<iostream>
#include<vector> //vector
#define inf 1e9
using namespace std;
int n,m,total=0;
vector<vector<int>>Map;
bool used[105][105]={0};
int dis[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
bool inrange(int x,int y){
return x>=0 && x<n && y>=0 && y<m;
}
int dfs(int x,int y){
total+=Map[x][y];
used[x][y]=true;
bool find_next=false;
int nextx=inf,nexty=inf,min_around=inf;
for(int i=0;i<4;i++){
int nx=x+dis[i][0],ny=y+dis[i][1];
if(inrange(nx,ny) && !used[nx][ny]){
find_next=true;
if(min_around > Map[nx][ny]){
min_around=Map[nx][ny];
nextx=nx; nexty=ny;
}
}
}
if(!find_next) return total;
return dfs(nextx,nexty);
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
vector<int>tmp;
for(int j=0;j<m;j++){
int x; cin>>x;
tmp.push_back(x);
}
Map.push_back(tmp);
}
int x=-1,y=-1,min_input=inf;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(min_input > Map[i][j]){
x=i,y=j;
min_input=Map[i][j];
}
}
}
cout<<dfs(x,y)<<"\n";
return 0;
}

## Python language
inf=float("inf")
n,m=map(int,input().split())
Map=[]
for i in range(n): Map.append([int(x) for x in input().split()])
x=y=-1
min_input=inf
for i in range(n):
for j in range(m):
if min_input > Map[i][j]:
x,y=i,j
min_input=Map[i][j]
used=[[False]*m for _ in range(n)]
dir=[[0,-1],[-1,0],[0,1],[1,0]]
total=0
def dfs(x,y):
global total
total+=Map[x][y]
used[x][y]=True
find_next=False
nextx=nexty=min_around=inf
for i,j in dir:
nx,ny=x+i,y+j
if (0<=nx<n) and (0<=ny<m) and not used[nx][ny]:
find_next=True
if min_around > Map[nx][ny]:
min_around=Map[nx][ny]
nextx,nexty=nx,ny
if find_next==False: return total
return dfs(nextx,nexty)
print(dfs(x,y))
