---
# System prepended metadata

title: Week 6
tags: [C++]

---

# 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存哪一個點要被擴展出去。
![](https://i.imgur.com/hEmNYep.png)
第一輪：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)


