j124 - 3. 石窟探險

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個整數序列，代表石窟中石室的編號。石室根據編號的奇偶性有不同數量的分支。要求計算石窟中所有相鄰石室編號差的絕對值的總和。

解題思路

這題可以使用深度優先搜尋 (DFS) 來模擬探險隊的走訪路徑。dfs 函數遞迴地走訪每個石室，並計算相鄰石室編號的差的絕對值。a 陣列儲存石室編號，ct 變數表示當前訪問的石室索引，ans 變數儲存總和。在每次訪問新石室時，計算與上一個石室編號的差的絕對值，並將其加到 ans 中。然後，根據當前石室編號的奇偶性，遞迴地訪問其分支。

複雜度分析

• 時間複雜度: O(N)，其中 N 是石室的數量。因為每個石室最多訪問一次。
• 空間複雜度: O(D)，其中 D 是樹的深度。這是因為 DFS 使用遞迴堆疊，其深度與樹的深度成正比。在最壞情況下，D 可能等於 N。

程式碼

#include <iostream>
using namespace std;
long long a[1000005],n,ct,ans;
void dfs(int p){
	if(a[ct]==0)return;
	if(p!=-1)ans+=abs(a[ct]-a[p]);
	p=ct;
	for(int i=0,n=2+a[ct]%2;i<n;++i){
		++ct;
		dfs(p);
	}
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> a[n++]);
	dfs(-1);
	cout << ans;
}