---
title: CP進階 05.basic graph theory
tags: 1th,CP進階
---

# CP進階 05.basic graph theory

[ppt](https://drive.google.com/file/d/1-qFo8Mafrr2c2cGId_tOcjOa2eVI-BG_/view?usp=sharing)
[ppt(revised)](https://drive.google.com/file/d/1OT1Pl9i4HYXiUy2FtM2Qst0U6xZn-Bo9/view?usp=sharing)
[ppt2](https://drive.google.com/file/d/1OlmbjgA_2uLgzo6Y2alMJ1M4d7Lyh6mG/view?usp=sharing)
[題單](https://codeforces.com/contestInvitation/20e2004cbd2e1dcf435dd54ecd01f618168d2422)
author: __Shioko

## flood fill algorithm

所謂的flood fill algorithm，指的就是像淹水一般，讓水從某一個點擴散開來。可以把它想成專門在方格圖上用的BFS(?

(一個flood fill的例子(圖由左到右))

#### 概念

基本上flood fill algorithm的核心想法和BFS差不多，都是依照距離原點的距離由近到遠依序尋訪，詳細的部分在課堂上已經講過，就不再贅述。

#### 實作

：「既然跟BFS差不多，代表說我可以直接套BFS，再稍微改一下就好了對吧？」

是的，基本上flood fill algorithm長得跟BFS很像，但是第一次寫的人常常會寫成這樣。

const int N = 100;
bool graph[N][N];  //false -> no obstacle, true -> have obstacle
bool visited[N][N];

void floodFill(pair<int, int> S) {
  queue<pair<int, int> > q;
  visited[S.first][S.second] = true;
  q.push(S);

  while(!q.empty()) {
    pair<int, int> now = q.front();
    q.pop();

    if (!visited[now.first + 1][now.second] and !graph[now.first + 1][now.second]) {
      visited[now.first + 1][now.second] = true;
      q.push(make_pair(now.first + 1, now.second));
    }
    if (!visited[now.first - 1][now.second] and !graph[now.first - 1][now.second]) {
      visited[now.first - 1][now.second] = true;
      q.push(make_pair(now.first - 1, now.second));
    }
    if (!visited[now.first][now.second + 1] and !graph[now.first][now.second + 1]) {
      visited[now.first][now.second + 1] = true;
      q.push(make_pair(now.first, now.second + 1));
    }
    if (!visited[now.first][now.second - 1] and !graph[now.first][now.second - 1]) {
      visited[now.first][now.second - 1] = true;
      q.push(make_pair(now.first, now.second - 1));
    }
  }
}

光是4方位的擴散就要4個if，那如果今天要寫的是8方位擴散，或著是西洋棋裡的騎士步怎麼辦？難道要寫8個if嗎？

稍微觀察一下這份code，可以發現每個if裡面除了index稍微不一樣以外，在做的事是相同的，因此我們可以用一點巧思，把所有擴散的方位用陣列存起來，讓它變成一個for迴圈就能搞定的事。

就像這樣：

const int N = 100;
bool graph[N][N];  //false -> no obstacle, true -> have obstacle
bool visited[N][N];

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

void floodFill(pair<int, int> S) {
  queue<pair<int, int> > q;
  visited[S.first][S.second] = true;
  q.push(S);

  while(!q.empty()) {
    pair<int, int> now = q.front();
    q.pop();

    for(int i = 0; i < 4; i++) {
      pair<int, int> nxt = make_pair(now.first + dx[i], now.second + dy[i]);
      if (!visited[nxt.first][nxt.second] and !graph[nxt.first][nxt.second]) {
        visited[nxt.first][nxt.second] = true;
        q.push(nxt);
      }
    }
  }
}

透過用陣列去儲存所有擴散的方向，就可以將一堆if壓成一個for迴圈能搞定的東西，並且能夠輕鬆地擴充功能，改成8方位擴散只要改一下陣列內容就好了！

const int dx[8] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dy[8] = {1, 0, -1, -1, -1, 0, 1, 1};

當然，如果你想要在方格圖上用一般的BFS也不是不行，只要在每個相鄰的方格之間建邊即可，只是這樣擴充性不好，耗費的空間也很大...

#### 一個小技巧

在做flood fill的時候，有時候可能會尋訪到陣列的邊界外面，因此要寫很惱人的邊界判斷，不過其實只要在圖的外圍圍一圈障礙物就可以不用判斷邊界了喔～


## 額外練習題

[ZJ c126.](https://zerojudge.tw/ShowProblem?problemid=c126) BST還原(經典題)
[CSES Counting Rooms](https://cses.fi/problemset/task/1192) (flood fill模板題)