e567 - 12503 - Robot Instructions

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個機器人在一維座標軸上移動，根據給定的指令序列計算機器人的最終位置。指令包括向左移動、向右移動，以及重複之前的指令。

解題思路

這題的核心是模擬機器人的移動過程。我們使用一個整數變數 x 來追蹤機器人的當前位置，初始化為 0。對於每一條指令，我們根據指令的類型更新 x 的值。如果指令是 "LEFT"，則 x 減 1；如果指令是 "RIGHT"，則 x 加 1；如果指令是 "SAME AS i"，則執行第 i 條指令相同的操作。為了實現 "SAME AS i"，我們使用一個整數陣列 a 來儲存每一條指令的移動量。a[i] 儲存第 i+1 條指令的移動量。在處理完所有指令後，x 的值就是機器人的最終位置。

複雜度分析

• 時間複雜度: O(n)，其中 n 是指令的數量。我們需要遍歷所有指令一次。
• 空間複雜度: O(n)，我們使用一個大小為 n 的陣列 a 來儲存指令的移動量。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	int t,n;
	cin >> t;
	while(t--){
		cin >> n;
		int x=0,ss,a[n];
		string s;
		for(int i=0;i<n;++i){
			cin >> s;
			if(s=="LEFT")
				a[i]=-1;
			else if(s=="RIGHT")
				a[i]=1;
			else{
				cin >> s >> ss;
				a[i]=a[ss-1];
			}
			x+=a[i];
		}
		cout << x << "\n";
	}
}