---
title: 8/24 晚上筆記 BFS
tags: 基礎算法
---

# GCD

using namespace std;
int a,b;
__gcd(a,b);

int gcd(int x, int y){
    if(x == 0)return y;
    return gcd(y%x, x);
}

# BFS (Breadth First Search)

https://zerojudge.tw/ShowProblem?problemid=e584
https://zerojudge.tw/ShowProblem?problemid=c124

queue
priority_queue
狀態、轉移
1->2
1->3
2->4
2->5

\ 1 2 3 4
- - - -
1 | S 1 2 3
2 | 1 2 3 4
3 | 2 # # 5
4 | 3 # E 6
5 | 4 5 6 7 -> E=7
queue = {~(2,1), (1,2)~, ...}
(1,1)->(2,1), (1,2)
(2,1)->(2,2), (3,1)
(1,2)->(1,3)
...

# 作業 (solve puzzle by using DFS & BFS)
***～兩題都寫一寫吧～***

[PA Zerojudge e584](https://zerojudge.tw/ShowProblem?problemid=e584)
[PB Zerojudge c124](https://zerojudge.tw/ShowProblem?problemid=c124)