k731 - 1. 路徑偵測
題目描述
題目給定一系列的二維平面座標，模擬從 (0, 0) 開始的移動路徑。每次移動只能是水平或垂直方向，且相鄰點的座標差值不大於 100。目標是計算路徑中左轉、右轉和迴轉的次數。
解題思路
這題可以使用貪心策略和模擬的方法來解決。我們從起始位置 (0, 0) 開始，並記錄當前的方向（初始方向為向右）。對於每個給定的座標點，我們根據該點與前一個點的相對位置來判斷轉彎的方向。
- 如果 x 座標增加，表示繼續向右移動。
- 如果 x 座標減少，表示向左移動。
- 如果 y 座標增加，表示向上移動。
- 如果 y 座標減少，表示向下移動。
根據當前方向和新的方向，我們可以判斷轉彎的類型：
- 如果方向改變了 90 度，則為左轉或右轉。
- 如果方向改變了 180 度，則為迴轉。
程式碼中 w 變數代表當前方向，0 代表上，1 代表下，2 代表左，3 代表右。程式會迭代每個座標點，計算轉彎的次數，並更新當前方向。
複雜度分析
- 時間複雜度: O(n)，其中 n 是座標點的數量。因為程式需要迭代每個座標點一次。
- 空間複雜度: O(1)，因為程式只使用了幾個常數大小的變數來存儲狀態。
程式碼
#include <iostream>
using namespace std;
int n,x,y,r,l,b,w=3,lx,ly;
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> x >> y;
int nw;
if(x>lx)nw=3;
else if(x<lx)nw=2;
else if(y>ly)nw=0;
else nw=1;
if(w==0){//u
if(nw==1)++b;
else if(nw==2)++l;
else if(nw==3)++r;
}
else if(w==1){//d
if(nw==0)++b;
else if(nw==2)++r;
else if(nw==3)++l;
}
else if(w==2){//l
if(nw==1)++l;
else if(nw==0)++r;
else if(nw==3)++b;
}
else{//r
if(nw==1)++r;
else if(nw==2)++b;
else if(nw==0)++l;
}
w=nw;
lx=x;
ly=y;
}
cout << l << ' ' << r << " " << b;
}