# 01BFS 能解决的问题

$0-1BFS$ 用来解决，== 在最短路中，花费的代价为 0 和 1 的时候，要求代价最少 == 的问题

有着 $BFS$ 的特性
当代价为 $0$ 的时候，把这一步放在双端队列的队首
代价为 $1$ 的时候，放在队尾（不需要代价的先计算）

# 例题

# 小明的游戏

# 题目大意

小明最近喜欢玩一个游戏。给定一个 $n \times m$ 的棋盘，上面有两种格子 # 和 @ 。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是 $0$ ，否则费用是 $1$ 。请编程计算从起始位置移动到目标位置的最小花费。

# 数据范围

对于 $100\%$ 的数据满足： $1 \le n, m \le 500$ .

# 题解

还是 $01~BFS$

遇到相同的就 $push$ 到队列首部

不同的就

push

到队列尾部

C++

int n, m, a, b, c, d, dis[N][N];
char s[N][N];

bool inside(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void bfs() {
    memset(dis, 0x3f, sizeof dis);

    deque<PII> q;
    q.push_back({a, b});
    dis[a][b] = 0;

    while (q.size()) {
        auto [x, y] = q.front();
        q.pop_front();

        for (int i = 1; i <= 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            if (!inside(nx, ny))
                continue;
            
            if (s[nx][ny] == s[x][y] && dis[nx][ny] > dis[x][y])
                dis[nx][ny] = dis[x][y], q.push_front({nx, ny});
            if (s[nx][ny] != s[x][y] && dis[nx][ny] > dis[x][y] + 1)
                dis[nx][ny] = dis[x][y] + 1, q.push_back({nx, ny});
        }
    }
}

void solve () {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];
    cin >> a >> b >> c >> d, a++, b++, c++, d++;
    
    bfs();

    cout << dis[c][d] << endl;
}

# Takahashi the Wall Breaker

# 题目大意

高桥居住的小镇被划分成一个由 $H$ 行和 $W$ 列组成的网格。每个单元格要么是一条路，要么是一堵墙
我们把从上面 $(1\leq i \leq H)$ 起第 $i$ 行，从左边 $(1\leq j \leq W)$ 起第 $j$ 列的单元格称为单元格 $(i,j)$
每个单元格的信息由长度为 $W$ 的 $H$ 字符串 $S_1,S_2,...,S_H$ 提供。具体来说：

如果 $S_i$ 的 $j-th$ 字符是 $(1\leq i \leq H,1\leq j\leq W)$ 是 . ，那么 $(i,j)$ 单元格就是一条路
如果是 # ，那么 $(i,j)$ 单元格就是一堵墙

他可以按任意顺序重复执行以下两种操作：

移动到相邻的单元格（向上、向下、向左或向右），该单元格位于小镇内且是一条道路。
从四个方向（上、下、左或右）中选择一个，然后朝该方向踢一脚
- 当他踢出一脚时，如果该格是一堵墙，则该格就会变成一条路
- 如果距离最多 $2$ 步的一些单元格在城镇之外，则仍然可以进行前踢，但城镇之外的任何东西都不会改变
  他从 $(A,B)$ 单元格开始，想要移动到 $(C,D)$ 单元格的鱼店。
  可以保证他起始的单元格和有鱼店的单元格都是道路。
  求他到达鱼店所需的最少个前踢

# 数据范围

$1\leq H,W \leq 1000$

# 题解

使用 $0-1~BFS$

如果是需要前踢的，就放在队列尾部

如果是可以直接走的，放在队列头部

C++

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

int n, m, dist[N][N];
int a, b, c, d;
char s[N][N];

bool inside(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void bfs() {
    memset(dist, 0x3f, sizeof dist);
    deque<PII> q;
    dist[a][b] = 0;
    q.push_front({a, b});

    while (q.size()) {
        auto [x, y] = q.front();
        q.pop_front();
        if (x == c && y == d)
            break;

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 2; j++) {
                int nx = x + j * dx[i], ny = y + j * dy[i];

                if (!inside(nx, ny))
                    break;
                
                if (s[nx][ny] == '.') {
                    if (j == 1 && dist[nx][ny] > dist[x][y])
                        dist[nx][ny] = dist[x][y], q.push_front({nx, ny});
                }
                else {
                    if (dist[nx][ny] > dist[x][y] + 1)
                        dist[nx][ny] = dist[x][y] + 1, q.push_back({nx, ny});
                }
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];
    cin >> a >> b >> c >> d;

    bfs();

    cout << dist[c][d] << endl;
}

# 01BFS 能解决的问题

# 例题

# 小明的游戏

# 题目大意

# 数据范围

# 题解

# Takahashi the Wall Breaker

# 题目大意

# 数据范围

# 题解

ABC-400

数据库范式