GabWiki | GabWiki

BFS

平面坐标系中模拟向周围 BFS。

C++

const int DIR[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向
const int DIR[][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}}; // 八个方向

void bfs(int x, int y) {
    queue<PII> que;
    // ...
    while (!que.empty()) {
        auto pr = que.front();
        que.pop();
        int x = pr.first, y = pr.second;
        // ...
        for (auto& DIR : DIRS) {
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && /* 其它条件 */) {
            	que.push({nx, ny});
                // ...
            }
        }
    }
}

const int DIR[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向
const int DIR[][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}}; // 八个方向

void bfs(int x, int y) {
    queue<PII> que;
    // ...
    while (!que.empty()) {
        auto pr = que.front();
        que.pop();
        int x = pr.first, y = pr.second;
        // ...
        for (auto& DIR : DIRS) {
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && /* 其它条件 */) {
            	que.push({nx, ny});
                // ...
            }
        }
    }
}

求「最少能从初始状态到达结束状态的步数」问题。

Java

import java.util.*;
import java.io.*;

public class Main {
    // 状态对象
    static class State {
        T content; // 状态
        int step; // 步数

        State(T content, int step) {
            // 初始化
            this.content = content;
            this.step = step;
        }

        // 重写equals方法对比状态是否相同
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof State)) return false;
            State s = (State) obj;
            // 对比状态
            // ...
        }

        // 重写hashCode方法用于存入集合 以便于快速确认状态的存在与否
        @Override
        public int hashCode() {
            // ...
        }

        // 由当前状态生成新的状态
        State newFrom(T content) {
            // ...
            return new State(content, step + 1);
        }
    }

    static State origin, target;
    
    public static void main(String[] args) throws IOException {
        // 输入状态 初始状态的步数皆为 0
        origin = new State(/* 初始状态 */, 0);
        target = new State(/* 目标状态 */, 0);
        // 输出结果(最少能从初始状态到达结束状态的步数)
        System.out.println(bfs());
    }

    static int bfs() {
        Queue<State> que = new LinkedList<>(); // BFS辅助队列
    	Set<State> vis = new HashSet<>(); // 判断状态是否已经见到过 用于剪枝
        que.offer(origin); // 放入初始状态
        while (!que.isEmpty()) {
            // 取出队尾状态
            State state = que.poll();
            // base case: 当前状态和达到目标则直接返回步数即是最短步数
            if (state.equals(target)) return state.step;
            // 枚举所有合法的状态转移
            for (eachValid in possibilities) {
                // 生成新状态
                State newState = state.newFrom(eachValid);
                // 若新生成的状态在以前没遇到过就把它加入队列与集合
                if (!set.contains(newState)) {
                    set.add(newState);
                    que.add(newState);
                }
            }
        }
        return -1;
    }
}

import java.util.*;
import java.io.*;

public class Main {
    // 状态对象
    static class State {
        T content; // 状态
        int step; // 步数

        State(T content, int step) {
            // 初始化
            this.content = content;
            this.step = step;
        }

        // 重写equals方法对比状态是否相同
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof State)) return false;
            State s = (State) obj;
            // 对比状态
            // ...
        }

        // 重写hashCode方法用于存入集合 以便于快速确认状态的存在与否
        @Override
        public int hashCode() {
            // ...
        }

        // 由当前状态生成新的状态
        State newFrom(T content) {
            // ...
            return new State(content, step + 1);
        }
    }

    static State origin, target;
    
    public static void main(String[] args) throws IOException {
        // 输入状态 初始状态的步数皆为 0
        origin = new State(/* 初始状态 */, 0);
        target = new State(/* 目标状态 */, 0);
        // 输出结果(最少能从初始状态到达结束状态的步数)
        System.out.println(bfs());
    }

    static int bfs() {
        Queue<State> que = new LinkedList<>(); // BFS辅助队列
    	Set<State> vis = new HashSet<>(); // 判断状态是否已经见到过 用于剪枝
        que.offer(origin); // 放入初始状态
        while (!que.isEmpty()) {
            // 取出队尾状态
            State state = que.poll();
            // base case: 当前状态和达到目标则直接返回步数即是最短步数
            if (state.equals(target)) return state.step;
            // 枚举所有合法的状态转移
            for (eachValid in possibilities) {
                // 生成新状态
                State newState = state.newFrom(eachValid);
                // 若新生成的状态在以前没遇到过就把它加入队列与集合
                if (!set.contains(newState)) {
                    set.add(newState);
                    que.add(newState);
                }
            }
        }
        return -1;
    }
}

BFS ​

BFS