关于后端:某东Java工程师笔试题解含BFS通用通俗模板

题目

大抵就是 n 行 m 列二维地图 A 在 (x,y)，B 在(a,b)。地图中有障碍物“#”示意不能通行，“.”示意能够通行，A 每次能够往上、下、左、右行走。
判断 A 是否能胜利走到 B 的地位

题解

思路就是 BFS (套用 BFS 的模板框架) 判断条件为以后坐标是否与 B 的统一

BFS 框架模板(Java)

//BFS 算法框架

boolean[][] mark = new boolean[n][m]; // 拜访标记
static int[][] go = {{0, -1}, {1, 0}, {-1, 0}, {0, 1}}; // 方向向量

static class State
{
    int x,y; // 坐标地位
    int step; // 搜寻步数记录
}

boolean Check(State s)
{
    // 边界判断
  return s.x>=0&&s.x<n&&s.y>0&&s.y<=m;
}

void BFS(State st)
{
    queue<State> q;
    State now,next;
    st.step = 0; // 步数清零;
    q.add(st); // 入队;
    while(!q.isEmpty())
    {now = q.poll(); // 队首元素出队；if(now == 指标状态) // 呈现指标状态，此时的 step 为最小值，做做相干解决后退出即可；{
            ……;
            return ....;
        }
        // 如果没有到指标状态
            for(int i=0;i<4;i++)
            {next.x = now.x + go[i][0];// 依照规定生成下一个状态
                next.y = now.y + go[i][1];
                if(CheckState(next)&&(依据题目批改条件)&&!mark) // 未越界、未被拜访、满足题目条件
                {
                    next.step = now.step + 1;
                    mark[next.x][next.y]=true;
                    q.add(next);
                }
            }
    }
}

public static void main(String[] args)
{
    // 输出
    BFS();
    // 输入
  
}

题解代码

public class AandB {
    // 初始化节点
    static class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public Node() {}
    }
    // 初始化全局变量
    static int n;
    static int m;
    // 行走的方向
    static int[][] dir = {{0, -1}, {1, 0}, {-1, 0}, {0, 1}};
    //a、b 代表各自的坐标
    static int ax = -1;
    static int ay = -1;
    static int bx = -1;
    static int by = -1;
    public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
        int total = scanner.nextint();
        while (total-- > 0) {n = scanner.nextint();
            m = scanner.nextint();
            Boolean[][] visit = new Boolean[n][m];
            // 拜访标记
            String[] map = new String[n];
            for (int i = 0; i < n; i++) {map[i] = scanner.next();}
                          // 初始化坐标
            for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i].charAt(j) == 'B') {
                        bx = i;
                        by = j;
                    }
                    if (map[i].charAt(j) == 'A') {
                        ax = i;
                        ay = j;
                    }
                }
            }
            if (bfs(ax, ay, map, visit)) {System.out.println("yes");
            } else {System.out.println("no");
            }
        }
    }
        // 越界
    static Boolean check(Node node) {return node.x >= 0 && node.x < n && node.y >= 0 && node.y < m;}
    static Boolean bfs(int x, int y, String[] map, Boolean[][] visit) {Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x, y));
        while (!queue.isEmpty()) {Node node = queue.poll();
            if (node.x == bx && node.y == by) {return true;}
            for (int i = 0; i < 4; i++) {Node next = new Node();
                next.x = node.x + dir[i][0];
                next.y = node.y + dir[i][1];
                // 判断条件
                if (check(next) && (map[next.x].charAt(next.y) == '.' || map[next.x].charAt(next.y) == 'B') && !visit[next.x][next.y]) {visit[next.x][next.y] = true;
                    queue.add(next);
                }
            }
        }
        return false;
    }
}

输入输出数据

2   // 两组数据
2 2  // n 行 m 列
.B
A.
2 2
#B
A#