---
# System prepended metadata

title: PUPC 2024 Problem C - Sky Stairway

---

# PUPC 2024 Problem C - Sky Stairway
### 題意:
你要從雲端階梯的第一朵雲（位置 0）一路跳到最後一朵雲（位置 𝑛−1），
雲有兩種：
* 0 是 Cumulus（積雲），可以踩上去。
* 1 是 Thunderhead（雷雨雲），不能踩。

求==從第一朵雲跳到最後一朵的最少步數是多少==？

規則如下：
* 只能踩在 0 的雲上，不能踩 1。
* 每次只能跳 1 或 2 步 (只能移動到下一朵或下下朵雲)。
* 如果沒辦法走到最後一朵，輸出 -1。
### Sample Input:
第一行代表有幾組測資，輸入直到EOF。
每組測資有兩行:
1. 第一行代表總共有 n 朵雲。
2. 第二行有 n 個布林值，代表每朵雲的類型。
```=
3
7
0 1 0 0 0 1 0
8
0 0 1 1 1 0 1 0
7
0 0 1 0 0 1 0
```
### Sample Output:
輸出所需花費的最小步數或無法抵達 (-1)。
```=
3
-1
4
```
### 程式碼:
我知道我這篇的程式寫得很糟（邏輯混亂）🤣
之後再重寫
```cpp=
#include <iostream>
#include <queue>
using namespace std;

int main() {
	int c, n, tmp; cin >> c;
	while (c--) {
		cin >> n;
		deque<bool> dq;
		bool pos = true;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			cin >> tmp;
			if (tmp == 0) cnt++;
			if (!dq.empty()) {
				if (tmp != dq.back()) {
					dq.clear();
					dq.push_back(tmp);
				}
				else if (tmp == 1) {
					pos = false;
				}
				else if (tmp == 0 && dq.size() == 2) {
					cnt--;
					dq.pop_back();
				}
				else {
					dq.push_back(tmp);
				}
			}
			else {
				dq.push_back(tmp);
			}
		}
		if (pos) cout << cnt - 1 << endl;
		else cout << -1 << endl;
	}
	return 0;
}
```