---
tags: 線上讀書會筆記
title: Week 37 題解
---

# PC:
範測一：
2
2 1
1 2
:::success
解法：每個座標點當作一個節點，並且如果兩個節點之間可以直接到達（X座標或Y座標相同），則兩個點之間連一條無向邊。最後檢查總共幾個連通塊，將數量減一即為答案。

Time complexity: $O(n^2)$
:::

# PD:
範測一：
7 3

1234567
L ---X--X
R -X--XX-

status: location of ninja, height of water
status: (ninja's height, ninja's side, water's height)
queue = {}
cur_status = (6, L, 3)
6+k = 6+3 > n => done

:::success
解法：BFS，將忍者的位置和目前水位高度存於狀態中，並使用三種題目給的移動方式進行轉移。

Time complexity: $O(n)$
:::