POJ1028–Wab导航 java代码例子

POJ 1028 - WAB 导航是一个经典的Java算法题，主要涉及路径搜索，通常涉及到图的深度优先搜索(DFS)或广度优先搜索(BFS)。以下是使用DFS的一个基本示例：

import java.util.*;

class Node {
    int x;
    int y;
    List<Node> edges; // 存储相邻节点

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.edges = new ArrayList<>();
    }
}

public class WABNavigation {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

    public int findPath(Node start, Node end) {
        dfs(start, end, new HashSet<>(), new boolean[grid.length][grid[0].length]);
        return pathLength;
    }

    private void dfs(Node current, Node target, Set<Node> visited, boolean[] visitedGrid) {
        if (current.equals(target)) {
            pathLength++;
            return;
        }

        visited.add(current);
        visitedGrid[current.x][current.y] = true;

        for (Node neighbor : current.edges) {
            int newX = current.x + DIRECTIONS[neighborDirection][0];
            int newY = current.y + DIRECTIONS[neighborDirection][1];

            if (isValidMove(newX, newY) && !visitedGrid[newX][newY]) {
                dfs(neighbor, target, visited, visitedGrid);
            }
        }
    }

    // 添加检查边界、障碍物等其他条件的 isValidMove() 方法
    private boolean isValidMove(int x, int y) {
        // 根据题目规则判断坐标是否合法
    }

    private int pathLength;
}

在这个示例中，`findPath`函数首先调用`dfs`来寻找从起点到终点的路径，`dfs`函数采用递归的方式，每次尝试向四个方向移动，同时记录已经访问过的节点和位置。当找到目标节点时，返回当前路径长度。