# Week 6
###### tags: `C++`
> STL容器簡介
今日目標：
- [ ] 了解電腦儲存資料方式
- [ ] STL用途
- [ ] 學會使用vector
- [ ] 了解queue使用方法並實作Flood Fill。
---
[TOC]
## Part 1: 記憶體概念複習
1. 陣列名稱
Q：b是什麼？
A：記憶體位置
```cpp=
int b[5] = {2, 4, 5};
cout << b << ' ' << *b << endl;
cout << b + 1 << ' ' << *(b+1) << endl;
cout << b + 2 << ' ' << *(b+2) << endl;
```
Output
```shell
0x16b4a7250 2
0x16b4a7254 4
0x16b4a7258 5
```
2. 記憶體位址
Q：為什麼a的值沒有被修改？
A：修改的是b，兩個記憶體位置不同
```cpp=
int a = 5;
int b = a;
b = 10;
cout << a << endl;
```
3. 指標與地址
Q：為什麼a的值改變了？請說明以下程式碼
A：
```cpp=
int a = 5;
// pa的型別為「int的指標」，也就是int型別變數的「位址」。
int *pa = &a;
*pa = 100;
cout << a << endl;
```
## Part 2: vector介紹
Q：vector與array的差別？
A：
- 取值$𝑂(1)$
- 尾端加值$𝑂(1)$
- 插入數值或刪除$O(n)$
### 常用語法
```cpp=
vector<int> v; // 宣告
vector<int> v1 = {2, 5};
vector<int> v2(5); // 五個預定值 {0, 0, 0, 0, 0}
vector<int> v3(5, 20); // 五個20 {20, 20, 20, 20, 20}
vector<int> v4(v3); // v4 = v3
// 宣告後就可以當array去用了
cout << v1[0] << endl; // 取值 O(1) output: 20
// array沒有的工能
v1.push_back(4); // 在陣列後方加4 變成{2, 3, 4}
cout << v1.size() << endl; // vector大小（存多少東西） output: 3
sort(v1.begin(), v1.end()); // 和array的sort比較一下 sort(a, a+5)
// v.begin()很像位址，但又不是。
reverse(v1.begin(), v1.end()); // v1 = {5, 4, 2}
// 有但幾乎用不到的語法
v1.insert(v1.begin(), 3); // 在最前面新增數字3 v1 = {3, 5, 4, 2}
v1.erase(v1.begin()+2); // 刪除index2的元素 v1 = {3, 5, 2}
```
### 題目常用
```cpp=
int n;
cin >> n;
// 根據輸入n宣告vector大小
vector<int> v(n); // 宣告一個vector，空間預設為n。
// 輸入n個數字
for(int i = 0; i < v.size(); i++) {
cin >> v[i];
}
// 輸出vector裡的東西 - method 1
for(int i = 0; i < v.size(); i++) {
cout << v[i] << endl;
}
// 輸出vector裡的東西 - method 2
for(int x : v) { // 很像python的寫法，把vector裡的東西遍歷一遍。
cout << x << endl;
}
```
### 二維
vector + vector
```cpp=
vector<vector<int> > v;
```
vector + array
```cpp=
vector<int> v[10005];
vector<array<int, 100005> > v2;
```
Q：為什麼插入和刪除元素很花時間？
A：
Q：描述一個狀況不能用array只能用vector。
A：
## 其他常用STL容器
### 序列型容器
- vector
- deque
- queue
- stack
### 非序列型容器
- set
- map
- priority_queue
> 再更後面才會用到的
> - multiset
> - unordered_map
可參考連結
- [陽明交大PCCA 2022 Winter Camp - STL](https://youtu.be/Pp4tgANoWC4)
## Part3: Flood Fill
Q：`queue`的常用語法？
A：
[資訊之芽講義](https://sprout.tw/algo2022/ppt_pdf/week03/flood_fill.pdf)
[資訊之芽影片](https://youtu.be/vZa63ofCehM)
### 存資料
```cpp=
/*
2*3的方格
1 2 3
4 5 6
*/
int p[1005][1005];
p[0][0] = 1;
p[0][1] = 2;
p[0][2] = 3;
p[1][0] = 4;
p[1][1] = 5;
p[1][2] = 6;
int n = 2, m = 3;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> p[i][j]
}
}
```
### 四周的點
```cpp=
int x = 5, y = 5;
cout << x + 1 << ' ' << y << endl; // 6 5
cout << x - 1 << ' ' << y << endl; // 4 5
cout << x << ' ' << y + 1 << endl; // 5 6
cout<< x << ' ' << y - 1 << endl; // 5 4
int dx = {0, 0, 1, -1};
int dy = {1, -1, 0, 0};
for(int k = 0; k < 4; k++) {
cout << x + dx[k] << ' ' << y + dy[k] << endl;
}
```
> 注意超出邊界
### 儲存座標點
```cpp=
// 自定義struct
struct Point {
int x, y;
};
Point p = {2, 2};
cout << p.x << ' ' << p.y << endl;
```
```cpp=
// 使用pair
pair<int, int> p = {2, 2};
cout << p.first << ' ' << p.second << endl;
```
```cpp=
// 偷懶少打字
#define X first
#define Y second
pair<int, int> p = {2, 2};
cout << p.X << ' ' << p.Y << endl;
```
### 使用queue擴展
queue存哪一個點要被擴展出去。
第一輪：queue = {1}
第二輪：queue = {2, 3, 4, 5}
第三輪：queue = {3, 4, 5, 6, 7, 8}
...
轉成座標
第一輪：queue = {(2, 2)}
第二輪：queue = {(1, 2), (2, 1), (2, 3), (3, 2)}
第三輪：queue = {(1, 2), (2, 1), (2, 3), (3, 2), (0, 2), (1, 1), (1, 3)}
```cpp=
queue<pair<int, int> > q;
q.push({2, 2});
while(q.empty() == false) {
pair<int, int> cur = q.front();
q.pop();
// 把當前點擴展出去加到queue裡
}
```
題單
- [zerojudge f170: m5a1-尋找小狗(Dog)](https://zerojudge.tw/ShowProblem?problemid=f170)
:::spoiler Code
``` cpp
#include <iostream>
#include <queue>
#define X first
#define Y second
#define MAX_N 1005
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, x, y, mp[MAX_N][MAX_N], vis[MAX_N][MAX_N]{}, ans = 0;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
queue<pair<int, int>> q;
cin >> n >> x >> y;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> mp[i][j];
}
}
q.push({x, y});
vis[x][y] = 1;
while(!q.empty()){
pair<int, int> cur = q.front();
q.pop();
x = cur.X, y = cur.Y;
ans++;
for(int k = 0; k < 4; k++){
int xi = x + dx[k], yi = y + dy[k];
if(xi < 0 || xi >= n || yi < 0 || yi >= n) continue;
else if(vis[xi][yi]) continue;
else if(abs(mp[xi][yi] - mp[x][y]) > 2) continue;
else{
q.push({xi, yi});
vis[xi][yi] = 1;
}
}
}
cout << ans << "\n";
}
```
:::
- [zerojudge d537: 4. 染色遊戲](https://zerojudge.tw/ShowProblem?problemid=d537)
Google Drive
Gist
Clipboard
Sign in with Wallet
