2019/06/15 機器人的路徑

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))

相關文章

分享此文：