---
tags: 搜索
title: 真‧基礎搜索方法
---
# 基礎搜索方法:

- BinS（二分搜）
- DFS（深度優先搜索）
- BFS（廣度優先搜索）

其實不只這些，這些只是在高中的程式競賽常用的方法～

:::success
## Binary Search

- 我要解決這個問題：
https://codeforces.com/problemset/problem/474/B

- 非專業＆非google翻譯：

給n堆物品，每堆物品A[i]個，每個物品被編碼，第一堆編碼1~A[1]，第二堆編碼A[1]+1~A[2]+1，and so on.

給m個查詢，每個查詢是一個數字Q[i]，代表物品編碼。

對於每筆查詢輸出物品Q[i]在第幾堆。

constrains:
N <= 10^5
M <= 10^5

(N)
A[1] ~ A[n]
(M)
Q[1] ~ Q[m]

123 4567 89 01234
ooo oooo oo ooooo
:::

:::success
## DFS (Depth First Search) & BFS (Breadth First Search)

- 我要解決這個問題：
http://domen111.github.io/UVa-Easy-Viewer/?11094

- 非專業＆非google翻譯：

給定一個二維地圖，地圖上每一格只有兩種可能字元：l表示大陸（Land），w表示水域（Water）
給定Mijid在圖上的座標，求Mijid佔的那塊大陸以外的 最大的大陸的面積。

詳細輸入輸出說明請自行看題目XDD

5 5
wwwww
wwllw
wwwww
wllww
wwwww
1 3

- 解題思路：
陸塊的大小可以從Mijid所在位置的上，下，左，右四個方向延伸，
所以每個方向都試試看還有沒有大陸

int m,n;//長寬
bool vis[20][20];//0->沒走過，1->走過
char grid[20][20];//地圖

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

int dfs(int x, int y){//回傳大小
    //確保grid[x][y]是陸地
    int ret = 1;//現在這塊～
    vis[x][y] = 1;
    /*
    if(x > 0 && grid[x-1][y] == 'l')ret += dfs(x-1, y);//上
    if(x < m-1 && grid[x+1][y] == 'l')ret += dfs(x+1, y);//下
    if(y > 0 && grid[x][y-1] == 'l')ret += dfs(x, y-1);//左
    if(y < n-1 && grid[x][y+1] == 'l')ret += dfs(x, y+1);//右
    */
    for(int i = 0; i < 4; ++i){
        int nx = x + dx[i], ny = y + dy[i];//嘗試下一格
        if(0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == 'l' && !vis[nx][ny]){
            ret += dfs(nx, ny);
        }
    }
    return ret;
}

void solve(){
    int ans = 0;
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            if(!vis[i][j] && grid[i][j] == 'l'){
            ans = max(dfs(i, j), ans);
        }
    }
}

- 例題：
https://zerojudge.tw/ShowProblem?problemid=a982
:::