APCS實作解題:路徑偵測(112年6月)

題目:

https://zerojudge.tw/ShowProblem?problemid=k731

給一個二維平面,座標如同數學的二維座標(Y正為北,X正為東)。起始位置在 (0, 0),接下來會有 n 個座標,你需要按照這些座標點的順序移動,保證僅會垂直或水平方向上移動,不會斜向移動,且第一個點保證一定是X軸正的位置(初始方向向右)。

請輸出這條路徑中,左轉、右轉、迴轉的個數分別為多少。

解題思路:

  1. 變數d, 數值可以是 0,1, 2, 3代表方向上下左右. 因為題目保證一開始一定向右,所以d = 3
  2. 紀錄前一個座標px, py
  3. 如果現在向右,而y > py, 代表轉向上
  4. 如果目前向左,而y > py, 代表轉向右
  5. 如果目前向下,而y > py, 代表是迴轉
  6. 其他方向也是相同邏輯
  7. 不要粗心就可通過測資

Python詳解:

#1. 初始化一開始都是0次
L, R, T = 0, 0 ,0

n = int(input())

# px, py 代表前一個x, y的座標位置. 一開始是0, 0
px, py = 0, 0

d = 3 # 0, 1, 2, 3 # U, D, L, R

for i in range( n):

  arr = input().split()
  x = int(arr[0])
  y = int(arr[1])

  if x == px: # 垂直移動
    if y > py:
      if d ==1:
        T+=1
      elif d ==2:
        R += 1
      elif d == 3:
        L +=1
      d=0

    else:
      if d==0:
        T +=1
      elif d==2:
        L +=1
      elif d==3:
        R +=1
      d = 1
  else:
    if x > px:
      if d==0:
        R +=1
      elif d==1:
        L +=1
      elif d==2:
        T +=1
      d = 3
    else:
      if d==0:
        L +=1
      elif d ==1:
        R +=1
      elif d==3:
        T +=1
      d = 2

  px, py = x, y

print(L, R, T)